CODEWITHSUNDEEP
javascriptreactjsalgorithmsortingmergesort
Giriteja Bille
Giriteja Bille

Reputation: 166

Unable to figure out the bug in merge sort

I am trying to build a sorting visualiser and when I code the merge sort algorithm the returning array is always of length 1 and my algorithm seems perfectly fine and I don't know what's making it to return single length array element and I did try to debug using console statements and everything seems fine until it goes into recursion.

my main app.js code is here:

testSortingAlgo() {
       //here we are creating 100 arrays for checking the sorting algorithms
    for (let i = 0; i < 100; i++) {   
        const array = [];
        //creating different lengths of the array
        const length = randomIntFromInterval(1, 1000);
        console.log(length);
        for (let j = 0; j < length; j++) {
            //push all collection of negative and positive numbers
            array.push(randomIntFromInterval(-1000, 1000));
        }
        console.log(array.length);
        console.log(array.slice().length);
        //for sorting in javascript inbuilt function .we are passing (a, b) => (a - b) because inbult function 
        // checks from starting character so in case of (200,5) 5 is greater as first char of 5 is greater than
        // first char of 200 that is 2
        const javascriptSortedArray = array.slice().sort((a, b) => (a - b))
        const SortedArray = sortingAlgorithms.mergeSort(array.slice());
        console.log(arraysAreEqual(javascriptSortedArray, SortedArray));
    }
}

in this function I am checking for validation of my sorting algorithm. when I pass the array.slice() to the merge sort. The array is getting manipulated in the following code

export const mergeSort = array => {
    // for (let i = 0; i < array.length; i++) {
    //     console.log(array[i]);
    if (array.length <= 1) return array;
    
    const middleIdx = Math.floor(array.length / 2);
    const firstHalf = mergeSort(array.slice(0, middleIdx));
    const secondHalf = mergeSort(array.slice(middleIdx, array.length));
    const sortedArray = [];
    let i = 0, j = 0;
    while (i < firstHalf.length && j < secondHalf.length) {
        if (firstHalf[i] < secondHalf[j]) {
            sortedArray.push(firstHalf[i++]);
        } else {
            sortedArray.push(secondHalf[j++]);
        }
    }
    while (i < firstHalf.length) array.push(firstHalf[i++]);
    while (j < secondHalf.length) array.push(secondHalf[j++]);
    return sortedArray;   
}

and it's returning a single array element.

Upvotes: 2

Views: 96

Answers (1)

Karl Galvez
Karl Galvez

Reputation: 843

I think you're gonna kick yourself for this one, I've done it many times in the past.

while(i<firstHalf.length) array.push(firstHalf[i++]);
while(j<secondHalf.length) array.push(secondHalf[j++]);

I think you intend to push to sortedArray

Worked on this repl https://repl.it/repls/BisqueNewMultitasking#index.js

Upvotes: 1

Related Questions