ThePrimeagen / kata-machine

1.28k stars 1.27k forks source link

My Merge Sort impl would not pass the test? #49

Open MrWittman612 opened 1 year ago

MrWittman612 commented 1 year ago

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.

snel1496 commented 1 month ago

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