kata-machine
kata-machine copied to clipboard
My Merge Sort impl would not pass the test?
I implemented merge sort. However, it would not pass the test my code is below. I change the return output of merge_sort from a void to a numbers array.
function merge(arr1: number[], arr2: number[]): number[] {
let results = [];
let i = 0;
let j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr2[j] > arr1[i]) {
results.push(arr1[i]);
i++;
} else {
results.push(arr2[j]);
j++;
}
}
while (i < arr1.length) {
results.push(arr1[i]);
i++;
}
while (j < arr2.length) {
results.push(arr2[j]);
j++;
}
return results;
}
export default function merge_sort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
let mid = Math.floor(arr.length / 2);
let left = merge_sort(arr.slice(0, mid));
let right = merge_sort(arr.slice(mid));
return merge(left, right);
}
The original stub of code.
export default function merge_sort(arr: number[]): void {
}
I changed the test code from this
import merge_sort from "@code/MergeSort";
test("merge-sort", function () {
const arr = [9, 3, 7, 4, 69, 420, 42];
expect(arr).toEqual([3, 4, 7, 9, 42, 69, 420]);
});
To this and it passed.
import merge_sort from "@code/MergeSort";
test("merge-sort", function () {
const arr = [9, 3, 7, 4, 69, 420, 42];
const val = merge_sort(arr);
expect(val).toEqual([3, 4, 7, 9, 42, 69, 420]);
});
I am not sure if the test is wrong or if my implementation is incorrect.
merge sort is in memory sort, you are given a buffer of memory, you can sort it in place, then that object has changed and the original test works, also at a glance I am not positive you have solved merge sort properly anyway