function mergesort(mergeArray, compare = function (a, b) { return a <= b; }, tab="") { //delete the tab param
let middle = Math.floor(mergeArray.length / 2); //find the middle index
let mergedarr = mergeArray;
let larr = [], rarr = []; //stores the left and right halves of the parameter array
//param array has more than 1 element then split the array in two
if (mergeArray.length > 1) {
larr = mergeArray.slice(0, middle);
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Slicing at: " + mergeArray[middle] + "
";
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Left Slice: " + larr + "
";
larr = mergesort(larr, compare, tab + "| "); //sort the left half
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Left Sorted: " + larr + "
";
rarr = mergeArray.slice(middle);
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Right Slice: " + rarr + "
";
rarr = mergesort(rarr, compare, tab + "| "); //sort the right half
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Right Sorted: " + rarr + "
";
mergedarr = merge(larr, rarr, compare, tab); //merge the two halves
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Merged Left & Right: " + mergedarr + "
";
}
// /** delete this line **/ document.getElementById("output").innerHTML += tab + "MergeSort: " + mergedarr + "
";;
return mergedarr; //return the sorted array
}
function merge(leftArray, rightArray, compare = function (a, b) { return a <= b; }, tab="") { //delete the tab param
let merged = [];
let l = 0, r = 0;
//loop through both arrays comparing elements and pushing the smaller of the two onto the merged array
//loop ends when the shorter of the arrays has no more elements
while (l < leftArray.length && r < rightArray.length) {
if (compare(leftArray[l], rightArray[r])) {
merged.push(leftArray[l]);
l++;
}
else {
merged.push(rightArray[r]);
r++;
}
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Merging: " + merged + "
";
}
//loop through the longer array and push the rest of its elements
for (l; l < leftArray.length; l++) {
merged.push(leftArray[l]);
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Merging: " + merged + "
";
}
for (r; r < rightArray.length; r++) {
merged.push(rightArray[r]);
/** delete this line **/ document.getElementById("output").innerHTML += tab + "Merging: " + merged + "
";
}
return merged;
}