ts-ds / sort

Variable: sort

const sort: object;

Defined in: sort/index.ts:27

All sorting algorithms under short names: sort.quick(array).

Type Declaration

bubble

bubble: <T>(array, compareFn?) => void = bubbleSort;

Sorts an array in place using bubble sort.

Repeatedly walks through the array and swaps adjacent elements that are in the wrong order. After pass k the k largest elements are in their final places. Stops early when a pass makes no swaps.

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n)	O(n²)	O(n²)	O(1)	yes	yes

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	T[]	undefined	Array to sort. It is modified.
compareFn?	CompareFn<T>	defaultCompare	Order of elements, ascending by default.

Returns

void

Nothing — array itself is sorted.

counting

counting: (array) => void = countingSort;

Sorts an array of integers in place using counting sort (CLRS, chapter 8.2).

Not a comparison sort, so it is not bound by the Ω(n log n) lower bound. With k = max - min + 1:

1. count[v] — how many times each value v occurs;
2. prefix sums turn counts into positions: count[v] — how many values are <= v;
3. walking the input from the end, every value is placed at --count[v], which keeps equal values in their original order (the sort is stable).

Efficient when k is not much larger than n.

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n + k)	O(n + k)	O(n + k)	O(n + k)	yes	no¹

¹ The result is written back into array, but O(n + k) extra memory is used.

Parameters

Parameter	Type	Description
array	number[]	Integers to sort, negative values are allowed. It is modified.

Returns

void

Nothing — array itself is sorted in ascending order.

Throws

If a value is not an integer.

Throws

If max - min + 1 exceeds COUNTING_SORT_MAX_RANGE.

heap

heap: <T>(array, compareFn?) => void = heapSort;

Sorts an array in place using heap sort.

1. Builds a max-heap from the array: array[i] >= array[2i+1] and array[i] >= array[2i+2], so the largest element is at index 0.
2. Moves the largest element to the end, shrinks the heap by one and restores the heap property with siftDown. Repeats until the heap is empty.

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n log n)	O(n log n)	O(n log n)	O(1)	no	yes

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	T[]	undefined	Array to sort. It is modified.
compareFn?	CompareFn<T>	defaultCompare	Order of elements, ascending by default.

Returns

void

Nothing — array itself is sorted.

insertion

insertion: <T>(array, compareFn?) => void = insertionSort;

Sorts an array in place using insertion sort.

Keeps the prefix array[0..i-1] sorted and inserts array[i] into it, shifting greater elements one position to the right. Fast on small and nearly sorted arrays.

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n)	O(n²)	O(n²)	O(1)	yes	yes

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	T[]	undefined	Array to sort. It is modified.
compareFn?	CompareFn<T>	defaultCompare	Order of elements, ascending by default.

Returns

void

Nothing — array itself is sorted.

merge

merge: <T>(array, compareFn?) => void = mergeSort;

Sorts an array in place using top-down merge sort.

Divide and conquer: splits the range in two halves, sorts each half recursively and merges the two sorted halves. Merging copies the range into a buffer and writes the elements back in order, always taking from the left half on ties — this keeps the sort stable.

If the halves are already in order (left.last <= right.first) the merge is skipped, so an already sorted array takes O(n).

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n)	O(n log n)	O(n log n)	O(n)	yes	no¹

¹ The result is written back into array, but an O(n) buffer is used.

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	T[]	undefined	Array to sort. It is modified.
compareFn?	CompareFn<T>	defaultCompare	Order of elements, ascending by default.

Returns

void

Nothing — array itself is sorted.

quick

quick: <T>(array, compareFn?) => void = quickSort;

Sorts an array in place using quick sort.

Divide and conquer: picks a pivot, partitions the range so that elements before the pivot are not greater and elements after it are not less, then sorts both parts recursively.

Details that make it reliable, as described by Hoare and Sedgewick:

• Hoare partitioning — two indexes move towards each other and swap elements that are on the wrong side. Both scans stop on elements equal to the pivot, so arrays with many duplicates are split evenly.
• Median-of-three pivot — the median of the first, middle and last element. Sorted and reversed arrays, the classic worst case for the "first/last element" pivot, become the best case.
• Recursion into the smaller part only, the larger part is handled by the loop — the call stack depth is at most O(log n) for any input.

The worst case O(n²) is still possible on specially crafted input. CLRS avoids it with high probability by choosing the pivot at random.

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n log n)	O(n log n)	O(n²)	O(log n)	no	yes

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	T[]	undefined	Array to sort. It is modified.
compareFn?	CompareFn<T>	defaultCompare	Order of elements, ascending by default.

Returns

void

Nothing — array itself is sorted.

radix

radix: (array) => void = radixSort;

Sorts an array of integers in place using LSD radix sort (CLRS, chapter 8.3).

Sorts by the last decimal digit, then by the one before it, and so on up to the most significant digit of the largest value. Each pass is a stable counting sort by one digit, so the order established by earlier (lower) digits is kept for equal higher digits.

Negative numbers are sorted by their absolute value separately and placed before the non-negative ones in reverse order.

With d digits in the largest absolute value and base b = 10:

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	yes	no¹

¹ The result is written back into array, but O(n) extra memory is used.

Parameters

Parameter	Type	Description
array	number[]	Integers to sort, negative values are allowed. It is modified.

Returns

void

Nothing — array itself is sorted in ascending order.

Throws

If a value is not an integer.

selection

selection: <T>(array, compareFn?) => void = selectionSort;

Sorts an array in place using selection sort.

On step i finds the smallest element of the unsorted part array[i..n-1] and swaps it with array[i]. Makes at most n - 1 swaps — useful when writing to memory is expensive.

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n²)	O(n²)	O(n²)	O(1)	no	yes

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	T[]	undefined	Array to sort. It is modified.
compareFn?	CompareFn<T>	defaultCompare	Order of elements, ascending by default.

Returns

void

Nothing — array itself is sorted.

shell

shell: <T>(array, compareFn?) => void = shellSort;

Sorts an array in place using Shell sort.

Insertion sort over elements that are gap positions apart, with the gap decreasing to 1. After a pass with gap h the array is "h-sorted", so the final pass with gap 1 (plain insertion sort) has little left to do.

Uses Knuth's gap sequence 1, 4, 13, 40, 121, … (h = 3h + 1), for which the worst case O(n^(3/2)) is proven. Shell's original sequence n/2, n/4, … is simpler but degrades to O(n²).

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n log n)	≈ O(n^(5/4))	O(n^(3/2))	O(1)	no	yes

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
array	T[]	undefined	Array to sort. It is modified.
compareFn?	CompareFn<T>	defaultCompare	Order of elements, ascending by default.

Returns

void

Nothing — array itself is sorted.