Class MergeSort<T>

MergeSort is a divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the two sorted halves. It is one of the most efficient sorting algorithms with a time complexity of O(n log n) in all cases.

The algorithm works by repeatedly dividing the array in half until each sub-array contains a single element (which is inherently sorted), and then merging those sorted sub-arrays back together. The merge operation compares elements from both sub-arrays and places them in the correct order.

MergeSort is stable (maintains relative order of equal elements) and has a space complexity of O(n) due to the auxiliary arrays needed for merging.

The time complexity is O(n log n) for best, average, and worst cases. The space complexity is O(n) for the auxiliary arrays.

Example

const mergeSort = new MergeSort([3, 4, 1]);
mergeSort.sort(); // returns new array with [1, 3, 4]
// or
MergeSort.sort([3, 4, 1]); // returns new array with [1, 3, 4]
Copy

Example

const mergeSort = new MergeSort(
 ['alice', 'bob', 'charlie', 'alex', 'gavin'],
 (a : string, b : string) => a.localeCompare(b)
);
mergeSort.sort(); // returns new array with ['alex', 'alice', 'bob', 'charlie', 'gavin']
Copy