@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

npm install @bemoje/arr-sort
npm install --save @bemoje/arr-sort
npm install --save-dev @bemoje/arr-sort

Usage

import arrSort from '@bemoje/arr-sort'

/**
 * OPTIONAL: REPLACE native Array.prototype.sort
 *
 * instead of calling sort(arr, options), you can also use arr.sort(options).
 *
 * 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.
 *
 * To activate this, do:
 */

arrSort.replaceNative()

/**
 * DATA: STRINGS
 * --------------
 */

let arr = ['5', '2', '4', '30', '1', '3']

/**
 * SORT ALPHABETICALLY BY DEFAULT
 * ------------------------------
 */

arrSort(arr)
//=> ['1', '2', '3', '30', '4', '5']

// OR
arr.sort()
//=> ['1', '2', '3', '30', '4', '5']

/**
 * DATA: NUMERIC VALUES
 * ----------------------
 */

arr = [5, 2, 4, 30, 1, 3]

/**
 * SORT NUMERICALLY
 * ----------------
 */

arrSort(arr, {
  numeric: true,
})
//=> [1, 2, 3, 4, 5, 30]

/**
 * SORT DESCENDING
 * ---------------
 */

arrSort(arr, {
  numeric: true,
  descending: true,
})
//=> [30, 5, 4, 3, 2, 1]

/**
 * DATA: PERSON OBJECTS
 * --------------------
 */

arr = [
  { name: 'john', age: 4 },
  { name: 'bill', age: 8 },
]

/**
 * SORT OBJECTS BY PROPERTY
 * ------------------------
 */

arrSort(arr, {
  by: 'name',
})

/* =>
  [
    { name: 'bill', age: 8 },
    { name: 'john', age: 4 },
  ]
*/

arrSort(arr, {
  numeric: true,
  by: 'age',
})

/* =>
  [
    { name: 'john', age: 4 },
    { name: 'bill', age: 8 },
  ]
*/

/**
 * DATA: PERSON OBJECTS WITH NESTED NAME OBJECTS
 * ---------------------------------------------
 */

arr = [
  { id: 0, name: { first: 'snoop', last: 'doggy' } },
  { id: 1, name: { first: 'kurt', last: 'qobain' } },
]

/**
 * SORT OBJECTS BY NESTED PROPERTY WITH DOT NOTATION
 * -------------------------------------------------
 */

arrSort(arr, {
  by: 'name.first',
})

/* =>
  [
    { id: 1, name: { first: 'kurt', last: 'qobain' } },
    { id: 0, name: { first: 'snoop', last: 'doggy' } },
  ]
*/

arrSort(arr, {
  by: 'name.last',
})

/* =>
  [
    { id: 0, name: { first: 'snoop', last: 'doggy' } },
    { id: 1, name: { first: 'kurt', last: 'qobain' } },
  ]
*/

/**
 * DATA: STRING DIRECTORY PATHS SPLIT IN ARRAYS
 * --------------------------------------------
 */

arr = [
  ['repo', 'src', 'compare.js'],
  ['repo', 'docs', 'index.html'],
]

/**
 * SORT BY ARRAY INDEX
 * -------------------
 */

arrSort(arr, {
  by: 2,
})

/* =>
  [
    ['repo', 'src', 'compare.js'],
    ['repo', 'docs', 'index.html'],
  ]
*/

arrSort(arr, {
  by: 1,
})

/* =>
  [
    ['repo', 'docs', 'index.html' ],
    ['repo', 'src', 'compare.js'],
  ]
*/

/**
 * DATA: DIRECTORY PATHS ARRAYS WITH SUB-ARRAYS
 * --------------------------------------------
 */

arr = [
  ['repo', 'src', ['compare', 'json']],
  ['repo', 'src', ['compare', 'ts']],
  ['repo', 'src', ['compare', 'js']],
]

/**
 * SORT ARRAYS AND SUB-ARRAYS RECURSIVELY
 * ------------------------------------
 */

arrSort(arr, {
  arrays: true,
})

/* =>
  [
    ['repo', 'src', ['compare', 'js']],
    ['repo', 'src', ['compare', 'json']],
    ['repo', 'src', ['compare', 'ts']],
  ]
*/

/**
 * DATA: IP ADDRESSES AS ARRAYS
 * ----------------------------
 */

arr = [
  [192, 168, 0, 1],
  [192, 168, 0, 101],
  [172, 0, 0, 1],
]

/**
 * SORT NUMERIC IP-ADDRESSES AS ARRAYS
 * -----------------------------------
 */

arrSort(arr, {
  numeric: true,
  arrays: true,
})

/* =>
  [
    [172, 0, 0, 1],
    [192, 168, 0, 1],
    [192, 168, 0, 101],
  ]
*/

/**
 * DATA: USER CLASS INSTANCES
 * --------------------------
 */

class User {
  constructor(firstName, lastName) {
    this.firstName = firstName
    this.lastName = lastName
  }
  get fullName() {
    return this.firstName + ' ' + this.lastName
  }
}

arr = [
  new User('john', 'doe'),
  new User('peter', 'wick'),
  new User('peter', 'johnson'),
  new User('les', 'paul'),
]

/**
 * SORT BY GETTER-FUNCTION
 * ------------------------
 */

arrSort(arr, {
  by: (user) => {
    return user.fullName
  },
})

/* =>
  [
    { firstName: 'john', lastName: 'doe'},
    { firstName: 'les', lastName: 'paul'},
    { firstName: 'peter', lastName: 'johnson'},
    { firstName: 'peter', lastName: 'wick'},
  ]
*/

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.

npm 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