As part of my learning journey, I decided to tackle implementing merge sort in Javascript. The mergeSort(unsortedArray) function is at the core of this implementation, taking an unsorted array and sorting it using the principles of merge sort. Within mergeSort(), there's a call to merge(leftArray, rightArray) which combines two sorted arrays into one sorted array.
The issue seems to lie within the merge() function. When I apply mergeSort to the array:[8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4,8] the resulting sorted array comes out as:[1,4,2,3,5,5,9,6,7,8,8]. On investigating, it appears that the problem arises when comparing leftArray[0] and rightArray[0] in the merge() function. Sometimes, instead of just the first index, rightArray[0] returns multiple values like 2,3 and 5,9. This mismatch causes discrepancies in the sorting process. Here's a breakdown of what happens inside merge() during this confusion:
Step1
leftArray:[4,5,6,7,8,8]
rightArray:[1,2,3,5,9]
result: []
Step2
leftArray[4,5,6,7,8,8]
rightArray[2,3,5,9]
result:[1]
Step3
(improper indexing... array[0] is returning two values)
leftArray[0]=4
rightArray[0]=2,3
leftArray[5,6,7,8,8]
rightArray[2,3,5,9]
result[1,4]
Step4
(improper indexing... array[0] is returning two values)
leftArray[0]=5
rightArray[0]=2,3
leftArray[5,6,7,8,8]
rightArray[5,9]
result[1,4,2,3]
...The inconsistency with array[0] resurfaces with rightArray[0] containing 5,9 next. Interestingly, when running merge() separately on leftArray=[4,5,6,7,8,8] and rightArray=[1,2,3,5,9], the result comes out correctly without any anomalies.
//Implement Merge Sort...
function mergeSort(unsortedArray) {
var leftArray = [];
var rightArray = [];
var result = [];
//Base Case of one element
if(unsortedArray.length <= 1){
//alert("Array is size 1 and value: " + unsortedArray);
return unsortedArray;
}
else{
var halfwayPoint = Math.round(unsortedArray.length/2);
//Sepertate unsortedArray into a left and right array
for(var i = 0; i < halfwayPoint; i++){
leftArray.push(unsortedArray[i]);
//alert("leftArray: "+ leftArray + " index i = " + i);
}
for(var i = halfwayPoint; i < unsortedArray.length; i++){
rightArray.push(unsortedArray[i]);
//alert("rightArray" + rightArray + " index i = " + i);
}
//alert("leftArray: " + leftArray + " rightArray: " + rightArray);
leftArray = mergeSort(leftArray);
rightArray = mergeSort(rightArray);
//alert("Arrays before merge = leftArray: " + leftArray + " rightArray: " + rightArray);
result = merge(leftArray, rightArray);
//alert("result: " + result);
}
return result;
}
//Helper function Merge for MergeSort
function merge(leftArray, rightArray)
{
var result = [];
while(leftArray.length > 0 && rightArray.length > 0){
//compare first items of both lists
//alert("top of while loop");
//alert("leftArray[0] = " + leftArray[0] + " rightArray[0] = " + rightArray[0]);
if(leftArray[0] >= rightArray[0]){
result.push(rightArray[0]);
//alert("result after push rightArray[0] " + result + " and rightArray before splice: "+ rightArray);
rightArray.splice(0,1);
//alert("rightArray after splce: " + rightArray);
}
else{
result.push(leftArray[0]);
//alert("result after push leftArray[0] " + result + " and leftArray before splice: "+ leftArray);
leftArray.splice(0,1);
//alert("leftArray after splce: " + leftArray);
}
}
//alert("before leftArray add");
if(leftArray.length > 0){
//alert("went into left array > 0 leftArray: " + leftArray);
result.push(leftArray);
}
//alert("before rightArray add");
if(rightArray.length > 0){
//alert("went into right array > 0 rightArray: " + rightArray);
result.push(rightArray);
}
//alert("result within merge function: " + result);
return result;
}
//Test Case
var unsortedArray = [8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4,8];
var sortedArray = mergeSort(unsortedArray);
lert(sortedArray);
//Problem is when Merge sort has left array and right array described below
//the merge function will yield proper result on left array and right array
//if called directly as it is below, however when merge is called through
//mergeSort with leftArray and rightArray as described below it yields
// improperResult below
var leftArray = [4,5,6,7,8,8];
var rightArray = [1,2,3,5,9];
var improperResult= [1,4,2,3,5,5,9,6,7,8,8];
var resultAct = merge(leftArray,rightArray);
alert(resultAct);<h1>MergeSort Problem</h1>