Security News
New Proposed CISA Mandate Would Require Critical Infrastructure to Report Ransom Payments Within 24 Hours
CISA has proposed a set of new rules that would require critical infrastructure to report cyber incidents and ransom payments.
array-timsort
Advanced tools
Fast JavaScript array sorting by implementing Python's Timsort algorithm
Weekly downloads
Readme
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.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.
Install the package with npm:
npm i array-timsort
And use it:
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:
function numberCompare (a, b) {
return a - b
}
const arr = [...]
sort(arr, numberCompare)
You can also sort only a specific subrange of the array:
sort(arr, 5, 10)
sort(arr, numberCompare, 5, 10)
A benchmark is provided in benchmark/index.js
. It compares the array-timsort
module against
the default array.sort
method in the numerical sorting of different types of integer array
(as described here):
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 array-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:
array-timsort
module's good performancearray.sort
in pure javascript
and counting element comparisonsTimSort 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 array-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
.
FAQs
Fast JavaScript array sorting by implementing Python's Timsort algorithm
The npm package array-timsort receives a total of 1,630,343 weekly downloads. As such, array-timsort popularity was classified as popular.
We found that array-timsort demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
CISA has proposed a set of new rules that would require critical infrastructure to report cyber incidents and ransom payments.
Security News
Redis is no longer OSS, breaking its explicit commitment to remain under the BSD 3-Clause License forever. This has angered contributors who are now working to fork the software.
Product
Socket AI now enables 'AI detected potential malware' alerts by default, ensuring users benefit from AI-powered state-of-the-art malware detection without needing to opt-in.