@bemoje/arr-sort

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 comparators made easy. Timsort: https://www.npmjs.com/package/timsort

Version

Travis CI

Dependencies

Stats

Donate

Installation

1npm install @bemoje/arr-sort
2npm install --save @bemoje/arr-sort
3npm install --save-dev @bemoje/arr-sort

Usage

1
2import arrSort from '@bemoje/arr-sort'
3
4/**
5 * OPTIONAL: REPLACE native Array.prototype.sort
6 *
7 * instead of calling sort(arr, options), you can also use arr.sort(options).
8 *
9 * It's generally not recommended to replace native class prototype methods, but since timsort is sturdy, tested and tried and proven to be considerably faster and IS truly a drop-in replacement, this might be a case where it could be considered a viable option.
10 *
11 * To activate this, do:
12 */
13
14arrSort.replaceNative()
15
16/**
17 * DATA: STRINGS
18 * --------------
19 */
20
21let arr = ['5', '2', '4', '30', '1', '3']
22
23/**
24 * SORT ALPHABETICALLY BY DEFAULT
25 * ------------------------------
26 */
27
28arrSort(arr)
29//=> ['1', '2', '3', '30', '4', '5']
30
31// OR
32arr.sort()
33//=> ['1', '2', '3', '30', '4', '5']
34
35/**
36 * DATA: NUMERIC VALUES
37 * ----------------------
38 */
39
40arr = [5, 2, 4, 30, 1, 3]
41
42/**
43 * SORT NUMERICALLY
44 * ----------------
45 */
46
47arrSort(arr, {
48  numeric: true,
49})
50//=> [1, 2, 3, 4, 5, 30]
51
52/**
53 * SORT DESCENDING
54 * ---------------
55 */
56
57arrSort(arr, {
58  numeric: true,
59  descending: true,
60})
61//=> [30, 5, 4, 3, 2, 1]
62
63/**
64 * DATA: PERSON OBJECTS
65 * --------------------
66 */
67
68arr = [
69  { name: 'john', age: 4 },
70  { name: 'bill', age: 8 },
71]
72
73/**
74 * SORT OBJECTS BY PROPERTY
75 * ------------------------
76 */
77
78arrSort(arr, {
79  by: 'name',
80})
81
82/* =>
83  [
84    { name: 'bill', age: 8 },
85    { name: 'john', age: 4 },
86  ]
87*/
88
89arrSort(arr, {
90  numeric: true,
91  by: 'age',
92})
93
94/* =>
95  [
96    { name: 'john', age: 4 },
97    { name: 'bill', age: 8 },
98  ]
99*/
100
101/**
102 * DATA: PERSON OBJECTS WITH NESTED NAME OBJECTS
103 * ---------------------------------------------
104 */
105
106arr = [
107  { id: 0, name: { first: 'snoop', last: 'doggy' } },
108  { id: 1, name: { first: 'kurt', last: 'qobain' } },
109]
110
111/**
112 * SORT OBJECTS BY NESTED PROPERTY WITH DOT NOTATION
113 * -------------------------------------------------
114 */
115
116arrSort(arr, {
117  by: 'name.first',
118})
119
120/* =>
121  [
122    { id: 1, name: { first: 'kurt', last: 'qobain' } },
123    { id: 0, name: { first: 'snoop', last: 'doggy' } },
124  ]
125*/
126
127arrSort(arr, {
128  by: 'name.last',
129})
130
131/* =>
132  [
133    { id: 0, name: { first: 'snoop', last: 'doggy' } },
134    { id: 1, name: { first: 'kurt', last: 'qobain' } },
135  ]
136*/
137
138/**
139 * DATA: STRING DIRECTORY PATHS SPLIT IN ARRAYS
140 * --------------------------------------------
141 */
142
143arr = [
144  ['repo', 'src', 'compare.js'],
145  ['repo', 'docs', 'index.html'],
146]
147
148/**
149 * SORT BY ARRAY INDEX
150 * -------------------
151 */
152
153arrSort(arr, {
154  by: 2,
155})
156
157/* =>
158  [
159    ['repo', 'src', 'compare.js'],
160    ['repo', 'docs', 'index.html'],
161  ]
162*/
163
164arrSort(arr, {
165  by: 1,
166})
167
168/* =>
169  [
170    ['repo', 'docs', 'index.html' ],
171    ['repo', 'src', 'compare.js'],
172  ]
173*/
174
175/**
176 * DATA: DIRECTORY PATHS ARRAYS WITH SUB-ARRAYS
177 * --------------------------------------------
178 */
179
180arr = [
181  ['repo', 'src', ['compare', 'json']],
182  ['repo', 'src', ['compare', 'ts']],
183  ['repo', 'src', ['compare', 'js']],
184]
185
186/**
187 * SORT ARRAYS AND SUB-ARRAYS RECURSIVELY
188 * ------------------------------------
189 */
190
191arrSort(arr, {
192  arrays: true,
193})
194
195/* =>
196  [
197    ['repo', 'src', ['compare', 'js']],
198    ['repo', 'src', ['compare', 'json']],
199    ['repo', 'src', ['compare', 'ts']],
200  ]
201*/
202
203/**
204 * DATA: IP ADDRESSES AS ARRAYS
205 * ----------------------------
206 */
207
208arr = [
209  [192, 168, 0, 1],
210  [192, 168, 0, 101],
211  [172, 0, 0, 1],
212]
213
214/**
215 * SORT NUMERIC IP-ADDRESSES AS ARRAYS
216 * -----------------------------------
217 */
218
219arrSort(arr, {
220  numeric: true,
221  arrays: true,
222})
223
224/* =>
225  [
226    [172, 0, 0, 1],
227    [192, 168, 0, 1],
228    [192, 168, 0, 101],
229  ]
230*/
231
232/**
233 * DATA: USER CLASS INSTANCES
234 * --------------------------
235 */
236
237class User {
238  constructor(firstName, lastName) {
239    this.firstName = firstName
240    this.lastName = lastName
241  }
242  get fullName() {
243    return this.firstName + ' ' + this.lastName
244  }
245}
246
247arr = [
248  new User('john', 'doe'),
249  new User('peter', 'wick'),
250  new User('peter', 'johnson'),
251  new User('les', 'paul'),
252]
253
254/**
255 * SORT BY GETTER-FUNCTION
256 * ------------------------
257 */
258
259arrSort(arr, {
260  by: (user) => {
261    return user.fullName
262  },
263})
264
265/* =>
266  [
267    { firstName: 'john', lastName: 'doe'},
268    { firstName: 'les', lastName: 'paul'},
269    { firstName: 'peter', lastName: 'johnson'},
270    { firstName: 'peter', lastName: 'wick'},
271  ]
272*/
273

Benchmark

Note: For short arrays, the speedup is insignificant or about the same. The more data there is, the faster the algorithms of timsort become, proportionally. Although timsort is a bit slower for short arrays, we're talking about a few milliseconds. So the overall improvement from Array.prototype.sort is quite unquestionable, imo.

ArrayType	Length	arrSort	Array.prototype.sort	Times faster
randomInt	10	715	954	1.33
randomInt	100	6878	14034	2.04
randomInt	1000	104597	210992	2.02
randomInt	10000	1560955	2804903	1.80
descendingInt	10	571	389	0.68
descendingInt	100	1122	1971	1.76
descendingInt	1000	4946	17183	3.47
descendingInt	10000	43319	170926	3.95
ascendingInt	10	534	369	0.69
ascendingInt	100	1022	1842	1.80
ascendingInt	1000	4460	16485	3.70
ascendingInt	10000	36601	157912	4.31
ascending3RandomExchangesInt	10	649	541	0.83
ascending3RandomExchangesInt	100	1757	3817	2.17
ascending3RandomExchangesInt	1000	6584	18115	2.75
ascending3RandomExchangesInt	10000	46194	172214	3.73
ascending10RandomEndInt	10	792	750	0.95
ascending10RandomEndInt	100	2430	3578	1.47
ascending10RandomEndInt	1000	8165	19885	2.44
ascending10RandomEndInt	10000	50357	176797	3.51
allEqualInt	10	526	397	0.75
allEqualInt	100	1048	1949	1.86
allEqualInt	1000	4400	16789	3.82
allEqualInt	10000	35976	162857	4.53
manyDuplicateInt	10	833	770	0.92
manyDuplicateInt	100	7806	11705	1.50
manyDuplicateInt	1000	110968	173539	1.56
manyDuplicateInt	10000	1491473	2255993	1.51
someDuplicateInt	10	797	747	0.94
someDuplicateInt	100	7797	11712	1.50
someDuplicateInt	1000	112189	174973	1.56
someDuplicateInt	10000	1526839	2301187	1.51

Tests

Uses Jest to test module functionality. Run tests to get coverage details.

1npm run test

API

Table of Contents

• arrSort

  • Parameters

  • replaceNative

• getter

  • Parameters

arrSort

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 comparators made easy. Timsort: https://www.npmjs.com/package/timsort

Parameters

• arr Array The array to sort.

• compare (function | object)? Comparator function or comparator-builder options. Defaults to alphabetical compararison.

  • compare.numeric boolean Sort numerically. Defaults to lexicographic/alphabetic sort. (optional, default false)

  • compare.descending boolean Sort in descending order. Defaults to ascending order. (optional, default false)

  • compare.array boolean Sort arrays. Nested arrays are also compared recursively. (optional, default false)

  • compare.by (number | string | getter) Sort by either array index, a callback(element): any - or by object keys with dot-notation support. (optional, default undefined)

• lo number? First element in the range (inclusive).

• hi number? Last element in the range.

Returns Array The sorted array

replaceNative

Replace the native Array.prototype.sort method with arrSort.

Returns void

getter

Callback type definition.

Type: Function

Parameters

• a any The value

Returns any The value to be compared