I am trying to write merge sort algorithm myself in javascript but I see that it is not working. I am taking a sample array [9,1,5,3] and trying to sort it. But it is giving me incorrect result but console shows me [3, undefined, undefined, 5]. I am unable to figure out myself where it is going wrong. Can anyone help me in this
function merge(arr, start, mid, end) {
const result = [];
let first = start;
let index = start;
let midNext = mid + 1;
while (first <= mid && midNext <= end) {
if (arr[first] <= arr[midNext]) {
result[index++] = arr[first++]
} else {
result[index++] = arr[midNext++]
console.log(result)
}
while (first <= mid) {
result[index++] = arr[first++]
console.log(result)
}
while (midNext <= end) {
result[index++] = arr[midNext++]
console.log(result)
}
}
for (let i = 0; i <= end; i++) {
arr[i] = result[i];
}
console.log(arr)
}
function mergeSort(arr, start, end) {
if (start == end) {
return start;
}
let midIndex = Math.floor(start + (end - start) / 2);
mergeSort(arr, start, midIndex);
mergeSort(arr, midIndex + 1, end);
merge(arr, start, midIndex, end)
}
Runnable javascript top down merge sort. Note that most libraries use a variation of bottom up merge sort, usually some mix of insertion and bottom up merge sort. Top down merge sort is mostly for academic purposes.
This example does a one time allocation of a second array and uses a pair of mutually recursive functions (each one calls the other), sortatoa(), sortatob() to change the direction of merge based on level of recursion. It will sort 1 million integers in a bit less than 250 ms on my system.
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
}
}The bug in your code is here: for (let i = 0; i <= end; i++)
When you copy the result array back to arr, you should write:
for (let i = start; i <= end; i++) {
arr[i] = result[i - start];
}
So I have taken a look at the problem and have written the mergesort algorithm in the most concise way I was able to. Comparing it with your given solution one can see that your mergeSort function is already pretty good. I think you overcomplicated the merging. In the merging part you would want to compare the next element that has not been added to the merged array which you can achieve with one while loop. So you do not need a start, mid and end index in the merge function.
function mergeSort(arr) {
const half = arr.length / 2;
if (arr.length <= 1) {
return arr;
}
const left = arr.splice(0, half);
const right = arr;
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let sortedArr = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
sortedArr.push(left.shift());
} else {
sortedArr.push(right.shift());
}
}
return [...sortedArr, ...left, ...right];
}
console.log(mergeSort([213,12323,53,12,453,231,12]));
If you have specific questions regarding my answer feel free to comment.