kata-machine icon indicating copy to clipboard operation
kata-machine copied to clipboard

My Merge Sort impl would not pass the test?

Open MrWittman612 opened this issue 1 year ago • 1 comments

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.

MrWittman612 avatar Jun 11 '23 22:06 MrWittman612

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

snel1496 avatar Sep 12 '24 02:09 snel1496