Name Last Update
..
build Loading commit data...
src Loading commit data...
.npmignore Loading commit data...
LICENSE.md Loading commit data...
README.md Loading commit data...
index.js Loading commit data...
package.json Loading commit data...

Node-TimSort: Fast Sorting for Node.js

Build Status npm version

An adaptive and stable sort algorithm based on merging that requires fewer than nlog(n) comparisons when run on partially sorted arrays. The algorithm uses O(n) memory and still runs in O(nlogn) (worst case) on random arrays.
This implementation is based on the original TimSort developed by Tim Peters for Python's lists (code here). TimSort has been also adopted in Java starting from version 7.

Acknowledgments

  • @novacrazy: ported the module to ES6/ES7 and made it available via bower
  • @kasperisager: implemented faster lexicographic comparison of small integers

Usage

Install the package with npm:

npm install --save timsort

And use it:

var TimSort = require('timsort');

var arr = [...];
TimSort.sort(arr);

You can also install it with bower:

bower install timsort

As array.sort() by default the timsort module sorts according to lexicographical order. You can also provide your own compare function (to sort any object) as:

function numberCompare(a,b) {
    return a-b;
}

var arr = [...];
var TimSort = require('timsort');
TimSort.sort(arr, numberCompare);

You can also sort only a specific subrange of the array:

TimSort.sort(arr, 5, 10);
TimSort.sort(arr, numberCompare, 5, 10);

Performance

A benchmark is provided in benchmark/index.js. It compares the timsort module against the default array.sort method in the numerical sorting of different types of integer array (as described here):

  • Random array
  • Descending array
  • Ascending array
  • Ascending array with 3 random exchanges
  • Ascending array with 10 random numbers in the end
  • Array of equal elements
  • Random Array with many duplicates
  • Random Array with some duplicates

For any of the array types the sorting is repeated several times and for different array sizes, average execution time is then printed. I run the benchmark on Node v6.3.1 (both pre-compiled and compiled from source, results are very similar), obtaining the following values:

Execution Time (ns) Speedup
Array Type Length TimSort.sort array.sort
Random 10 404 1583 3.91
100 7147 4442 0.62
1000 96395 59979 0.62
10000 1341044 6098065 4.55
Descending 10 180 1881 10.41
100 682 19210 28.14
1000 3809 185185 48.61
10000 35878 5392428 150.30
Ascending 10 173 816 4.69
100 578 18147 31.34
1000 2551 331993 130.12
10000 22098 5382446 243.57
Ascending + 3 Rand Exc 10 232 927 3.99
100 1059 15792 14.90
1000 3525 300708 85.29
10000 27455 4781370 174.15
Ascending + 10 Rand End 10 378 1425 3.77
100 1707 23346 13.67
1000 5818 334744 57.53
10000 38034 4985473 131.08
Equal Elements 10 164 766 4.68
100 520 3188 6.12
1000 2340 27971 11.95
10000 17011 281672 16.56
Many Repetitions 10 396 1482 3.74
100 7282 25267 3.47
1000 105528 420120 3.98
10000 1396120 5787399 4.15
Some Repetitions 10 390 1463 3.75
100 6678 20082 3.01
1000 104344 374103 3.59
10000 1333816 5474000 4.10

TimSort.sort is faster than array.sort on almost of the tested array types. In general, the more ordered the array is the better TimSort.sort performs with respect to array.sort (up to 243 times faster on already sorted arrays). And also, in general, the bigger the array the more we benefit from using the timsort module.

These data strongly depend on Node.js version and the machine on which the benchmark is run. I strongly encourage you to run the benchmark on your own setup with:

npm run benchmark

Please also notice that:

  • This benchmark is far from exhaustive. Several cases are not considered and the results must be taken as partial
  • inlining is surely playing an active role in timsort module's good performance
  • A more accurate comparison of the algorithms would require implementing array.sort in pure javascript and counting element comparisons

Stability

TimSort is stable which means that equal items maintain their relative order after sorting. Stability is a desirable property for a sorting algorithm. Consider the following array of items with an height and a weight.

[ 
  { height: 100, weight: 80 },
  { height: 90, weight: 90 },
  { height: 70, weight: 95 },
  { height: 100, weight: 100 },
  { height: 80, weight: 110 },
  { height: 110, weight: 115 },
  { height: 100, weight: 120 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 100, weight: 135 },
  { height: 75, weight: 140 },
  { height: 70, weight: 140 } 
]

Items are already sorted by weight. Sorting the array according to the item's height with the timsort module results in the following array:

[ 
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 70, weight: 140 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 80 },
  { height: 100, weight: 100 },
  { height: 100, weight: 120 },
  { height: 100, weight: 135 },
  { height: 110, weight: 115 } 
]

Items with the same height are still sorted by weight which means they preserved their relative order.

array.sort, instead, is not guarranteed to be stable. In Node v0.12.7 sorting the previous array by height with array.sort results in:

[ 
  { height: 70, weight: 140 },
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 100 },
  { height: 100, weight: 80 },
  { height: 100, weight: 135 },
  { height: 100, weight: 120 },
  { height: 110, weight: 115 } 
]

As you can see the sorting did not preserve weight ordering for items with the same height.