ts-ds / mergeSort
Function: mergeSort()
ts
function mergeSort<T>(array, compareFn?): void;Defined in: sort/merge/merge.ts:24
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.