Fast JavaScript array sorting by implementing Python's Timsort algorithm
npm install array-timsort

A fork of timsort with the following differences:
- array-timsort returns an array which records how the index of items have been sorted, while timsort returns undefined. See the example below.
- improves test coverage
- removes some dead code branches that could never be reached
- no longer built with UMD
``js
const {sort} = require('array-timsort')
const array = [3, 2, 1, 5]
sort(array) // returns [2, 1, 0, 4]
console.log(array) // [1, 2, 3, 5]
`
**
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.
- @novacrazy: ported the module to ES6/ES7 and made it available via bower
- @kasperisager: implemented faster lexicographic comparison of small integers
Install the package with npm:
`sh`
npm i array-timsort
And use it:
`js
const {sort} = require('array-timsort')
const arr = [...]
sort(arr)
`
As array.sort() by default the array-timsort module sorts according to
lexicographical order.
You can also provide your own compare function (to sort any object) as:
`js
function numberCompare (a, b) {
return a - b
}
const arr = [...]
sort(arr, numberCompare)
`
You can also sort only a specific subrange of the array:
`js`
sort(arr, 5, 10)
sort(arr, numberCompare, 5, 10)
A benchmark is provided in benchmark/index.js. It compares the array-timsort module againstarray.sort
the default 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.TimSort.sort
In general, the more ordered the array is the better performs with respect to array.sort (up to 243 times faster on already sorted arrays).array-timsort
And also, in general, the bigger the array the more we benefit from using
the 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 array-timsort module's good performancearray.sort
- A more accurate comparison of the algorithms would require implementing in pure javascript
and counting element comparisons
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.
`javascript`
[
{ 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 }
]weight
Items are already sorted by . Sorting the arrayheight
according to the item's with the array-timsort module`
results in the following array:javascript`
[
{ 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 }
]height
Items with the same 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.7height
sorting the previous array by with array.sort results in:`javascript`
[
{ 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 }
]weight
As you can see the sorting did not preserve ordering for items with theheight`.
same