Benchmark: Comb Sort vs. Native Sort

Script Preparation code:

var sampleData = [];
for (var i=0; i < 100000; i++){ 
  sampleData.push({value: (Math.floor(Math.random() * 10000))});
}

var selectorFn = function(x) { 
  return x.value;  
}

var combSort = function (source, selectorFn, sortDirection) {
    var result = source.slice();
    var count = result.length;
    var gap = count;
    var swapped = true;

    while (gap > 1 || swapped) {

      if (gap > 1) {
        gap = Math.floor(gap / 1.24733);
      }

      var i = 0;
      swapped = false;

      while ((i + gap) < count) {

        var item1 = result[i];
        var item2 = result[i + gap];

        if (shouldBeSwaped(selectorFn(item1), selectorFn(item2), selectorFn, sortDirection)) {
          result[i] = item2;
          result[i + gap] = item1;
          swapped = true;
        }

        i++;
      }
	}
  
    return result;
}

 var shouldBeSwaped = function(value, valueToCompare, selectorFn, sortDirection) {
 	var less = value > valueToCompare;
	return sortDirection === "asc" ? less : !less;
  }

​x
 
var sampleData = [];for (var i=0; i < 100000; i++){   sampleData.push({value: (Math.floor(Math.random() * 10000))});}​var selectorFn = function(x) {   return x.value;  }​var combSort = function (source, selectorFn, sortDirection) {    var result = source.slice();    var count = result.length;    var gap = count;    var swapped = true;​    while (gap > 1 || swapped) {​      if (gap > 1) {        gap = Math.floor(gap / 1.24733);      }​      var i = 0;      swapped = false;​      while ((i + gap) < count) {​        var item1 = result[i];        var item2 = result[i + gap];​        if (shouldBeSwaped(selectorFn(item1), selectorFn(item2), selectorFn, sortDirection)) {          result[i] = item2;          result[i + gap] = item1;          swapped = true;        }​        i++;      }    }      return result;}​ var shouldBeSwaped = function(value, valueToCompare, selectorFn, sortDirection) {    var less = value > valueToCompare;    return sortDirection === "asc" ? less : !less;  }

Tests:

Native Sort DESC

var order = "desc";

sampleData.sort(function(a,b){
	var x = selectorFn(a); var y = selectorFn(b);
	var res = ((x < y) ? -1 : ((x > y) ? 1 : 0));

	return order === "desc" ? -1*res : res;
})

 
var order = "desc";​sampleData.sort(function(a,b){    var x = selectorFn(a); var y = selectorFn(b);    var res = ((x < y) ? -1 : ((x > y) ? 1 : 0));​    return order === "desc" ? -1*res : res;})

Native Sort ASC

var order = "desc";

sampleData.sort(function(a,b){
	var x = selectorFn(a); var y = selectorFn(b);
	var res = ((x < y) ? -1 : ((x > y) ? 1 : 0));

	return order === "desc" ? -1*res : res;
})

 
var order = "desc";​sampleData.sort(function(a,b){    var x = selectorFn(a); var y = selectorFn(b);    var res = ((x < y) ? -1 : ((x > y) ? 1 : 0));​    return order === "desc" ? -1*res : res;})

Comb Sort DESC
var order = "asc"; combSort(sampleData, selectorFn, order);
var order = "asc";

combSort(sampleData, selectorFn, order);
Comb Sort ASC
var order = "asc"; combSort(sampleData, selectorFn, order);
var order = "asc";

combSort(sampleData, selectorFn, order);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Experimental features:

Memory measurements supported only in Chrome.
For precise memory measurements Chrome must be launched with --enable-precise-memory-info flag.
More information: Monitoring JavaScript Memory

Test case name	Result
Native Sort DESC
Native Sort ASC
Comb Sort DESC
Comb Sort ASC

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 8 years ago)

User agent: Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; rv:11.0) like Gecko

Browser/OS: IE 11 on Windows

View result in a separate tab

Test name	Executions per second
Native Sort DESC	3.5 Ops/sec
Native Sort ASC	3.4 Ops/sec
Comb Sort DESC	2.9 Ops/sec
Comb Sort ASC	2.9 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):

Benchmark Explanation

The provided benchmark compares the performance of two sorting algorithms: Native JavaScript sort and Comb Sort. The benchmark uses a sample dataset of 100,000 random integers and measures the execution time for each sorting algorithm in descending (ASC) and ascending (DESC) order.

Native JavaScript Sort

Native JavaScript sort is implemented using the sort() method with a custom comparison function that compares two elements based on their values. The comparison function returns an integer value indicating the direction of the sort:

-1 if the first element is less than the second
1 if the first element is greater than the second
0 if the elements are equal

The native JavaScript sort implementation uses a variation of the Timsort algorithm, which is a hybrid sorting algorithm derived from merge sort and insertion sort.

Comb Sort

Comb Sort is an optimized version of Bubble Sort that uses a combination of two techniques:

Gap reduction: The initial gap size is set to the length of the array, and then reduced by a factor of 1.24733 in each iteration.
Swapping direction: If the swap operation results in a reversal (i.e., the first element becomes larger than the second), the direction of the sort is reversed.

Pros and Cons

Native JavaScript Sort:

Pros:
- Well-established and widely supported algorithm
- Fast and efficient for large datasets
Cons:
- Not optimized for small datasets or nearly sorted arrays
- May not perform well for arrays with duplicate elements

Comb Sort:

Pros:
- Optimized for small datasets and nearly sorted arrays
- Reduces the number of comparisons required in each iteration
Cons:
- Requires more iterations to achieve the same performance as Native JavaScript Sort
- May not be as efficient for very large datasets

Library: Timsort

Timsort is a hybrid sorting algorithm that combines elements of merge sort and insertion sort. It is used as the underlying implementation for the native JavaScript sort() method.

Special JS Feature/ Syntax

This benchmark does not use any special JavaScript features or syntax, such as async/await, Promises, or modern ES6+ features.

Alternatives

Other sorting algorithms that could be compared to Native JavaScript Sort and Comb Sort include:

QuickSort
Merge Sort
Heap Sort
Radix Sort (for sorting large datasets of integers)
Insertion Sort (for very small datasets)

These alternatives may offer better performance or efficiency for specific use cases, but the trade-offs in terms of implementation complexity, cache friendliness, and stability must be carefully considered.

LLMs can make mistakes. Check important info.

**Benchmark Explanation**

**Native JavaScript Sort**

Native JavaScript sort is implemented using the `sort()` method with a custom comparison function that compares two elements based on their values. The comparison function returns an integer value indicating the direction of the sort:

* `-1` if the first element is less than the second
* `1` if the first element is greater than the second
* `0` if the elements are equal

The native JavaScript sort implementation uses a variation of the Timsort algorithm, which is a hybrid sorting algorithm derived from merge sort and insertion sort.

**Comb Sort**

Comb Sort is an optimized version of Bubble Sort that uses a combination of two techniques:

1. **Gap reduction**: The initial gap size is set to the length of the array, and then reduced by a factor of 1.24733 in each iteration.
2. **Swapping direction**: If the swap operation results in a reversal (i.e., the first element becomes larger than the second), the direction of the sort is reversed.

**Pros and Cons**

Native JavaScript Sort:

* Pros:
	+ Well-established and widely supported algorithm
	+ Fast and efficient for large datasets
* Cons:
	+ Not optimized for small datasets or nearly sorted arrays
	+ May not perform well for arrays with duplicate elements

Comb Sort:

* Pros:
	+ Optimized for small datasets and nearly sorted arrays
	+ Reduces the number of comparisons required in each iteration
* Cons:
	+ Requires more iterations to achieve the same performance as Native JavaScript Sort
	+ May not be as efficient for very large datasets

**Library: Timsort**

Timsort is a hybrid sorting algorithm that combines elements of merge sort and insertion sort. It is used as the underlying implementation for the native JavaScript `sort()` method.

**Special JS Feature/ Syntax**

This benchmark does not use any special JavaScript features or syntax, such as async/await, Promises, or modern ES6+ features.

**Alternatives**

Other sorting algorithms that could be compared to Native JavaScript Sort and Comb Sort include:

* QuickSort
* Merge Sort
* Heap Sort
* Radix Sort (for sorting large datasets of integers)
* Insertion Sort (for very small datasets)

Related benchmarks:

Comb Sort vs. Native Sort (version: 0)

Comparing performance of: Native Sort DESC vs Native Sort ASC vs Comb Sort DESC vs Comb Sort ASC

Created: 8 years ago by: Guest

Jump to the latest result