@santi100/sorting-lib

Santi's Sorting Library

• 🚀 Lightweight and fast
• 👴 ES3-compliant
• 📘 Comes with built-in TypeScript definitions
• 📑 Split into files (under cjs/) to import what's needed
• 💻 Portable between the browser and Node.js

What's this?

This is a library of sorting algorithms written in TypeScript. Currently, the library includes the following algorithms:

• Bubble sort
• Insertion sort
• Selection sort
• Merge sort
• Quick sort
• Bogo sort
• Radix sort
• Heap sort
• Counting sort
• Shell sort

Thanks to @codediodeio for the idea, taken from his video about sorting algorithms and its corresponding repo.

Installation

• Via NPM: npm install @santi100/sorting-lib
• Via Yarn: yarn add @santi100/sorting-lib
• Via PNPM: pnpm install @santi100/sorting-lib

API

• type SortComparator<T = unknown> = (a: T, b: T) => number; Comparator function for every sorting algorithm, except for radixSort. It's fully compatible with Array.prototype.sort's callback.

• type SortOrder = 'ascending' | 'descending'; Sorting order string. Must be either ascending or descending.

• interface SortOptions<T = unknown>; Shape of the opts object passed to every sorting algorithm, except for radixSort. See RadixSortOptions for the options specific to it.

  • comparator?: SortComparator<T>; Comparator function for every sorting algorithm, except for radixSort. It's fully compatible with Array.prototype.sort's callback. See SortComparator.
  • order?: SortOrder; Sorting order string. Must be either ascending or descending. See SortOrder.

• interface RadixSortOptions; Shape of the opts object exclusive to radixSort.

  • order?: SortOrder; Sorting order string. Must be either ascending or descending. See SortOrder.

• type CountingSortOptions = RadixSortOptions; (since 0.0.3) Shape of the opts object exclusive to countingSort.

• function bubbleSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[]; Sorts arr with bubble-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity: Quadratic ($O(n ^ 2)$).

• function insertionSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[]; Sorts arr with insertion-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity (average and worst-case): Quadratic ($O(n ^ 2)$).

Time complexity (best-case): Linear ($O(n)$).

• function selectionSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[]; Sorts arr with selection-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity (average and worst-case): Quadratic ($O(n ^ 2)$).

• function mergeSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[]; Sorts arr with merge-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity (average and worst-case): Quasi-linear ($O(n \log{n})$).

• function quickSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[]; Sorts arr with quick-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity (best and average): Quasi-linear ($O(n \log{n})$).

Time complexity (worst): Quadratic ($ O(n ^ 2) $).

• function bogoSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[]; Sorts arr with bogo-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity (average): Linear-factorial ($O((n!)(n))$).

Worst-case time complexity: Infinity ($O(∞)$).

• function radixSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[]; Sorts arr with radix-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity (best, average and worst): $O(n k)$, where $k$ is the number of digits or characters in the largest element.

• function heapSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[]; Sorts arr with heap-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity (best, average and worst): Quasi-linear ($O(n \log {n})$).

• function shellSort<T = unknown>(arr: T[], opts?: SortOptions<T>): T[];: Sorts arr with shell-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity: Depends on the gap sequence used. Best known is $O(n (log2(n) ^ 2))$.

• function countingSort(arr: number[], opts?: CountingSortOptions): T[];: Sorts arr with counting-sort and returns a new sorted array (i.e.: doesn't mutate arr). It takes the array to sort, and optional sorting options, and returns a sorted copy of arr.

Time complexity (best, average and worse): $O(n + k)$, where $k$ is the range of input (maximum element - minimum element + 1).

• function bozoSort<T = unknown>(array: T[]): T[]; Sorts an array using the Bozo Sort algorithm.

  Name	Description
  array	The array to be sorted.

• function bozoSort<T = unknown>(array: T[], opts: SortingOptions<T>): T[]; Sorts an array using the Bozo Sort algorithm.

  Name	Description
  array	The array to be sorted.
  opts	An object containing sorting options.

Usage

import { mergeSort, bozoSort } from '@santi100/sorting-lib'; // ESM
const { mergeSort, bozoSort } = require('@santi100/sorting-lib'); // CJS
const sorted = mergeSort([4, 2, 5, 1, 3]); // sorted = [1, 2, 3, 4, 5]
const descendingSorted = mergeSort([4, 2, 5, 1, 3], { order: 'descending' }); // descendingSorted = [5, 4, 3, 2, 1]
const objSorted = mergeSort(
	[
		{
			age: 23
		},
		{
			age: 12
		},
		{
			age: 30
		}
	],
	{ comparator: (a, b) => a.age - b.age }
); // returns [ { age: 12 }, { age: 23 }, { age: 30 }]
// You can do same for all algorithms, except for `radixSort`, which is limited to ints for now, so
// its only option is `order`.
const sortedArray = bozoSort(array);
console.log(sortedArray); // Output: [1, 2, 3]

Contribute

Wanna contribute? File an issue or pull request! Look at the contribution instructions and make sure you follow the contribution Code of Conduct.

*Hasn't been tested in an actual ES3 environment. Feel free to open an issue or pull request if you find any non-ES3 thing. See "Contribute" for instructions on how to do so.

^The source code is just a few kilobytes in size.