npmpackage.info

Gathering detailed insights and metrics for array-timsort

Other packages similar to array-timsort

@bemoje/arr-sort

1.0.2

Sort an array considerably faster than the native Array.prototype.sort as a drop-in replacement. Fork of of the famous timsort module, but this module allows for passing comparator-builder options instead of a comparator function. In short, advanced compa

array-timsort

Fast JavaScript array sorting by implementing Python's Timsort algorithm

1.0.3

MIT

JavaScript

2.16 kB

201,988,005 3

Installations

npm install array-timsort

Developer Guide

BETA

Typescript

No

Module System

CommonJS

Node Version

14.12.0

NPM Version

6.14.8 Pull Requests

Open

0

Total

0

Closed

0

Issues

Open

0

Total

0

Closed

0

Releases

Unable to fetch releases

Contributors

Unable to fetch Contributors

View all 4 contributors

Languages

JavaScript

JavaScript (100%)

Developer

kaelzhang

Download Statistics

Total Downloads

201,988,005

Last Day

585,006

Last Week

2,721,013

Last Month

11,945,320

Last Year

127,526,833

GitHub Statistics

3 Stars

53 Commits

3 Watching

1 Branches

4 Contributors

Bundle Size

5.92 kB

Minified

2.16 kB

Minified + Gzipped

Bundlephobia

Maintainers

Package Meta Information

Latest Version

1.0.3

Package Id

array-timsort@1.0.3

Size

8.95 kB

NPM Version

6.14.8

Node Version

14.12.0

Publised On

01 Oct 2020

Total Downloads

Cumulative downloads

Total Downloads

201,988,005

Last day

-6%

585,006

Compared to previous day

Last week

-14.5%

2,721,013

Compared to previous week

Last month

2.2%

11,945,320

Compared to previous month

Last year

153.7%

127,526,833

Compared to previous year

Daily Downloads

Weekly Downloads

Monthly Downloads

Yearly Downloads

Dev Dependencies

@ostai/eslint-config ava codecov eslint eslint-plugin-import eslint-plugin-mocha nyc

Versions

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

1const {sort} = require('array-timsort')
2
3const array = [3, 2, 1, 5]
4
5sort(array)  // returns [2, 1, 0, 4]
6
7console.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.

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:

1npm i array-timsort

And use it:

1const {sort} = require('array-timsort')
2
3const arr = [...]
4
5sort(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:

1function numberCompare (a, b) {
2    return a - b
3}
4
5const arr = [...]
6
7sort(arr, numberCompare)

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

1sort(arr, 5, 10)
2sort(arr, numberCompare, 5, 10)

Performance

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):

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	Speedup
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:

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 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.

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 array-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.

10

Binary-Artifacts

Determines if the project has generated executable (binary) artifacts in the source repository.

10

Vulnerabilities

Determines if the project has open, known unfixed vulnerabilities.

10

License

Determines if the project has defined a license.

0

Maintained

Determines if the project is "actively maintained".

0

Code-Review

Determines if the project requires human code review before pull requests (aka merge requests) are merged.

0

SAST

Determines if the project uses static code analysis.

0

CII-Best-Practices

Determines if the project has an OpenSSF (formerly CII) Best Practices Badge.

0

Security-Policy

Determines if the project has published a security policy.

0

Fuzzing

Determines if the project uses fuzzing.

0

Branch-Protection

Determines if the default and release branches are protected with GitHub's branch protection settings.

Score

3

/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