Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | 222x 1x 35x 35x 2x 1x 1x 1x 73x 6x 67x 35x 32x 32x 1x 35x 35x 35x 35x 144x 73x 6x 6x 67x 67x 71x 65x 65x 6x 6x 35x 1x 78x 35x 35x 35x 35x | import SortingOrder from "@src/util/SortingOrder.ts";
interface Split {
left: Array<number>;
right: Array<number>;
}
function split(input: Array<number>): Split {
const pivot = Math.floor(input.length / 2);
return {
left: input.slice(0, pivot),
right: input.slice(pivot),
};
}
enum Operand {
Left = 0,
Right = 1,
}
function whoGoesFirst(x: number, y: number, order: SortingOrder): Operand {
if (order === SortingOrder.Ascending && x <= y) {
return Operand.Left;
}
if (order === SortingOrder.Ascending && x > y) {
return Operand.Right;
}
if (order === SortingOrder.Descending && x <= y) {
return Operand.Right;
}
return Operand.Left;
}
function merge(
left: Array<number>,
right: Array<number>,
order: SortingOrder,
): Array<number> {
let leftIndex = 0;
let rightIndex = 0;
const sortedArray: Array<number> = [];
// while the left index or the right index are not out of bound
while (leftIndex < left.length || rightIndex < right.length) {
if (leftIndex < left.length && rightIndex < right.length) {
if (
whoGoesFirst(left[leftIndex], right[rightIndex], order) === Operand.Left
) {
sortedArray.push(left[leftIndex]);
leftIndex += 1;
} else {
sortedArray.push(right[rightIndex]);
rightIndex += 1;
}
} else if (leftIndex < left.length && rightIndex >= right.length) {
sortedArray.push(left[leftIndex]);
leftIndex += 1;
} else {
sortedArray.push(right[rightIndex]);
rightIndex += 1;
}
}
return sortedArray;
}
/**
* Sort the array of numbers in either ascending or descending order, applying the merge sort algorithm.
*
* - Time complexity: O(N log(N)) where N is the size of the array.
*
* @param input the array of numbers to sort.
* @param order specify the order of sorting: ascending or descending.
*/
export default function mergeSort(
input: Array<number> | null,
order: SortingOrder,
): Array<number> | null {
if (!Array.isArray(input) || input.length <= 1) return input;
const splitInput: Split = split(input);
// make sure to handle the case where the split returns null
const sortedLeft = mergeSort(splitInput.left, order) ?? [];
const sortedRight = mergeSort(splitInput.right, order) ?? [];
return merge(sortedLeft, sortedRight, order);
}
|