README.md



Node-TimSort: Fast Sorting for Node.js


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.