Gathering detailed insights and metrics for timsort
Installations
npm install timsortDeveloper Guide
BETA
Typescript
No
Module System
CommonJS
Node Version
6.3.1
NPM Version
3.10.3
Score
99.8
Supply Chain
99.6
Quality
75.4
Maintenance
100
Vulnerability
100
License
Releases
Unable to fetch releases
Contributors
3
Unable to fetch Contributors
Languages
1
JavaScript
JavaScript (100%)
Developer
mziccard
Download Statistics
Total Downloads
1,567,292,562
Last Day
503,187
Last Week
2,276,340
Last Month
10,563,176
Last Year
156,067,416
GitHub Statistics
245 Stars
35 Commits
37 Forks
3 Watching
2 Branches
3 Contributors
Bundle Size
5.79 kB
Minified
2.16 kB
Minified + Gzipped
Maintainers
1
Package Meta Information
Latest Version
0.3.0
Package Id
timsort@0.3.0
Size
12.96 kB
NPM Version
3.10.3
Node Version
6.3.1
Publised On
24 Jul 2016
Total Downloads
Cumulative downloads
Total Downloads
1,567,292,562
Last day
-5.3%
503,187
Compared to previous day
Last week
-19.6%
2,276,340
Compared to previous week
Last month
6.2%
10,563,176
Compared to previous month
Last year
-30%
156,067,416
Compared to previous year
Daily Downloads
Weekly Downloads
Monthly Downloads
Yearly Downloads
Versions
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:
1var TimSort = require('timsort'); 2 3var arr = [...]; 4TimSort.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:
1function numberCompare(a,b) { 2 return a-b; 3} 4 5var arr = [...]; 6var TimSort = require('timsort'); 7TimSort.sort(arr, numberCompare);
You can also sort only a specific subrange of the array:
1TimSort.sort(arr, 5, 10); 2TimSort.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
timsortmodule's good performance - A more accurate comparison of the algorithms would require implementing
array.sortin 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.
1[ 2 { height: 100, weight: 80 }, 3 { height: 90, weight: 90 }, 4 { height: 70, weight: 95 }, 5 { height: 100, weight: 100 }, 6 { height: 80, weight: 110 }, 7 { height: 110, weight: 115 }, 8 { height: 100, weight: 120 }, 9 { height: 70, weight: 125 }, 10 { height: 70, weight: 130 }, 11 { height: 100, weight: 135 }, 12 { height: 75, weight: 140 }, 13 { height: 70, weight: 140 } 14]
Items are already sorted by weight. Sorting the array
according to the item's height with the timsort module
results in the following array:
1[ 2 { height: 70, weight: 95 }, 3 { height: 70, weight: 125 }, 4 { height: 70, weight: 130 }, 5 { height: 70, weight: 140 }, 6 { height: 75, weight: 140 }, 7 { height: 80, weight: 110 }, 8 { height: 90, weight: 90 }, 9 { height: 100, weight: 80 }, 10 { height: 100, weight: 100 }, 11 { height: 100, weight: 120 }, 12 { height: 100, weight: 135 }, 13 { height: 110, weight: 115 } 14]
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:
1[ 2 { height: 70, weight: 140 }, 3 { height: 70, weight: 95 }, 4 { height: 70, weight: 125 }, 5 { height: 70, weight: 130 }, 6 { height: 75, weight: 140 }, 7 { height: 80, weight: 110 }, 8 { height: 90, weight: 90 }, 9 { height: 100, weight: 100 }, 10 { height: 100, weight: 80 }, 11 { height: 100, weight: 135 }, 12 { height: 100, weight: 120 }, 13 { height: 110, weight: 115 } 14]
As you can see the sorting did not preserve weight ordering for items with the
same height.
No vulnerabilities found.
Reason
no binaries found in the repo
Reason
license file detected
Details
- Info: project has a license file: LICENSE.md:0
- Info: FSF or OSI recognized license: MIT License: LICENSE.md:0
Reason
0 existing vulnerabilities detected
Reason
Found 2/14 approved changesets -- score normalized to 1
Reason
0 commit(s) and 0 issue activity found in the last 90 days -- score normalized to 0
Reason
no effort to earn an OpenSSF best practices badge detected
Reason
project is not fuzzed
Details
- Warn: no fuzzer integrations found
Reason
security policy file not detected
Details
- Warn: no security policy file detected
- Warn: no security file to analyze
- Warn: no security file to analyze
- Warn: no security file to analyze
Reason
branch protection not enabled on development/release branches
Details
- Warn: branch protection not enabled for branch 'master'
Reason
SAST tool is not run on all commits -- score normalized to 0
Details
- Warn: 0 commits out of 19 are checked with a SAST tool
Score
3.2
/10
Last Scanned on 2025-01-27
The Open Source Security Foundation is a cross-industry collaboration to improve the security of open source software (OSS). The Scorecard provides security health metrics for open source projects.
Learn More