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.
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
