Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
MrWittman612 opened this issue Jun 11, 2023 · 1 comment
Open

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

MrWittman612 opened this issue Jun 11, 2023 · 1 comment

Comments

@MrWittman612
Copy link

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
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants