I was trying to implement merge sort algorithm in JavaScript without built in methods like slice(), splice(), etc. It doesn’t work exactly I wish. Can you help me to figure out where is bug hidden? Getting output [3, 5, 5, 3, 7] instead of [3, 5, 5, 7, 8].
// Merge Sort implementation
// sort implementation
function sort(arr, start, mid, end) {
// Creation and filling the temp arrays
let lArray = [];
let rArray = [];
for (let i = 0; i <= mid - start; i++) {
lArray[i] = arr[start + i];
}
for (let j = 0; j <= end - mid - 1; j++) {
rArray[j] = arr[mid + 1 + j];
}
// Sorting and updating current array
let i = 0;
let j = 0;
let k = start;
while (i < lArray.length && j < rArray.length) {
if (lArray[i] < rArray[j]) {
arr[k] = lArray[i];
i++;
k++;
} else {
arr[k] = rArray[j];
j++;
k++;
}
}
// Handling last element in lArray or rArray
i < lArray.length ? arr[k] = lArray[i] : arr[k] = rArray[j];
}
// Recursive Merge Sort
function recursiveMergeSort(arr, start, end) {
if (start < end) {
let mid = Math.floor(((end) + start) / 2);
//console.log(start, end, mid);
recursiveMergeSort(arr, start, mid);
recursiveMergeSort(arr, mid + 1, end);
sort(arr, start, mid, end);
}
}
function mergeSort(arr) {
let start = 0;
let end = arr.length - 1;
recursiveMergeSort(arr, start, end);
return (arr)
}
console.log(mergeSort([5, 8, 3, 7, 5])); // Handling last element in lArray or rArray is not correct.
After merging arrays you have to check the rests and copy untreated tail if it does exist
while (i < lArray.length) {
arr[k] = lArray[i];
i++;
k++;
}
while (j < rArray.length) {
arr[k] = rArray[j];
j++;
k++;
}
Replacing ternary operator by this code gives correct results for given data
Example of a somewhat optimized version of top down merge sort. It does a one time allocation of a working array and uses a pair of mutually recursive functions to change the direction of merge for each level of recursion. Takes about 1/4 second to sort 1 million pseudo-random integers on my system:
// merge sort top down
function merge(a, b, bgn, mid, end) {
var i = bgn // left: a[bgn,mid)
var j = mid // right: a[mid,end)
var k = bgn // index for b[]
while(true){
if(a[i] <= a[j]){ // if left <= right
b[k++] = a[i++] // copy left
if(i < mid) // if not end of left
continue // continue back to while
do // else copy rest of right
b[k++] = a[j++]
while(j < end)
break // and break
} else { // else left > right
b[k++] = a[j++] // copy right
if(j < end) // if not end of right
continue // continue back to while
do // else copy rest of left
b[k++] = a[i++]
while(i < mid)
break // and break
}
}
}
function sortatob(a, b, bgn, end) { // sort a to b
if ((end-bgn) < 2){
b[bgn] = a[bgn]
return
}
var mid = Math.floor(bgn + (end - bgn) / 2)
sortatoa(a, b, bgn, mid)
sortatoa(a, b, mid, end)
merge(a, b, bgn, mid, end)
}
function sortatoa(a, b, bgn, end) { // sort a to a
if ((end-bgn) < 2)
return
var mid = Math.floor(bgn + (end - bgn) / 2)
sortatob(a, b, bgn, mid)
sortatob(a, b, mid, end)
merge(b, a, bgn, mid, end)
}
function mergesort(a) { // entry function
if(a.length < 2)
return
var b = new Array(a.length) // allocate temp array
sortatoa(a, b, 0, a.length) // start with sort a to a
}
var a = new Array(1000000)
for (i = 0; i < a.length; i++) {
a[i] = parseInt(Math.random() * 1000000000)
}
console.time('measure')
mergesort(a)
console.timeEnd('measure')
for (i = 1; i < a.length; i++) {
if(a[i-1] > a[i]){
console.log('error')
break
}
}