f-sort

A fast, small (~0.5 KB gzipped) and dependency-free JavaScript library to sort arrays. It uses quick sort internally to sort arrays in place, without recursion. Simply replace JavaScript's built-in Array.prototype.sort with f-sort's sort to see ~2x performance. This is especially for helpful for large arrays.

The cherry on top of the cake - it sorts numbers in the increasing order of value, out of the box, something that can not be said for JavaScript's native sort method :)

Installation

npm install f-sort
#OR
yarn add f-sort

API Reference

sort()

Definition:

sort(
    array: any[], // required
    comparator?: function, // optional
    pivotExtractor?: function // optional
) -> any[]

Parameters

1. array: any[] | Required | The array that will be sorted in place.

2. comparator: function(a: any, b: any) -> Number | Optional | A function used to compare two elements of the array. The function is passed two elements of the array, and it should return a number denoting the comparison of the two elements -

   1. comparator(a, b) < 0 - a < b
   2. comparator(a, b) === 0 - a === b
   3. comparator(a, b) > 0 - a > b

   Default value

   (a, b) => a - b;

   This default comparator sorts the array in increasing order if it comprises of numbers.

   Provided comparator

   f-sort provides 2 comparators out of the box -

   1. ascNumberComparator - Sorts numbers in ascending order (default comparator)
   2. descNumberComparator - Sorts numbers in descending order

   These can be imported as -

   import { comparators } from "f-sort";

   And used as

   sort(arr, comparators.ascNumberComparator); // ascending order
   sort(arr, comparators.descNumberComparator); // descending order

3. pivotExtractor: function(arr: any[], left: Number, right: Number) -> Number | Optional | A function that returns the pivot to partition the array between left (inclusive) and right (exclusive) indices. This parameter is exposed for more advance uses - the default value works for most cases. The returned pivot must be in the range in the following range - left <= pivot < right>

   Default value

   The default pivot extractor returns the middle element of the range between left and right.

   // Return the index between left and right
   // Same as Math.floor((left + right) / 2), but faster.
   (arr, left, right) => (left + right) >>> 1;

   The pivotExtractor argument can be used to implement more advanced pivot selection techniques like quick select.

   Provided pivotExtractors

   f-sort provides 4 pivot extractors out of the box -

   1. mid - Returns the middle index of the range as the pivot (Default)
   2. first - Returns the first index of the range (left) as the pivot
   3. last - Returns the last index of the range (right - 1) as the pivot
   4. random - Returns a random index in the range left to right - 1

   These can be import as -

   import { pivotExtractors } from "f-sort";

   And used as

   sort(arr, undefined, pivotExtractors.mid);
   sort(arr, undefined, pivotExtractors.first);
   sort(arr, undefined, pivotExtractors.last);
   sort(arr, undefined, pivotExtractors.random);

Usage and examples

Import the sort function from f-sort, and simply pass the array to sort. The function does not create a copy of the array, and sorts it in-place, and returns the sorted array.

import { sort } from "f-sort";
const arr = [-1, 1, 100, 20000, 8];
const sortedArr = sort(arr);
console.log("sortedArr:", sortedArr);
console.log("arr:", arr);

The following code outputs -

arr: [ -1, 1, 8, 100, 20000 ]
sortedArr: [ -1, 1, 8, 100, 20000 ]

Notice, the returned array is just a reference to the array passed into the function. If you wish to make a sorted copy of the array, clone the array before passing it into sort, like so -

import { sort } from "f-sort";
const arr = [-1, 1, 100, 20000, 8];
const sortedArr = [...arr];
sort(sortedArr);
console.log(sortedArr);
console.log(arr);

The following code outputs -

arr: [ -1, 1, 100, 20000, 8 ]
sortedArr: [ -1, 1, 8, 100, 20000 ]

Using a comparator

A comparator can be passed to sort() to help sort the array in a custom order, or to sort incomparable types, like objects.

1. Sorting numbers by the squares of their values

   const arr = [-2, 1, 2, -3];
   sort(arr, (a, b) => a * a - b * b);
   console.log("arr:", arr);

   The following snippet outputs -

   arr: [ 1, 2, -2, -3 ]
   

2. Sorting an array of objects, of the shape -

   { x: Number, y: Number };

   The following snippet sorts an array of such objects by the value of their x property.

   const arr = [
   	{ x: 100, y: 21 },
   	{ x: -50, y: 1000 },
   	{ x: 99, y: 100 },
   	{ x: 200, y: -100 },
   ];
   sort(arr, (a, b) => a.x - b.x);
   console.log("arr:", arr);

   The following code outputs -

   arr: [
       { x: -50, y: 1000 },
       { x: 99, y: 100 },
       { x: 100, y: 21 },
       { x: 200, y: -100 }
   ]