Implementing merge sort in Javascript

Question

So I'm working on Khan Academy's Algorithms course, and am trying to implement a recursive merge sort in Javascript. Here is my code so far:

var mergeSort = function(array, p, r) {
    if(r>p) {
        var q = floor(r/2);
        mergeSort(array, p, q);
        mergeSort(array, q+1, r);
        merge(array, p, q, r);
    }
};

merge is a function provided by Khan Academy to merge the subarrays back together. It is giving me the error: 'Uncaught RangeError: Maximum call stack size exceeded'.

EDIT: More details: I am fairly sure the error is in my code, there code is purposefully obfuscated and unreadable because the user needs to implement it themselves in a later challenge.

Here is the code that actually calls the mergeSort function initially and declares the array:

var array = [14, 7, 3, 12, 9, 11, 6, 2];
mergeSort(array, 0, array.length-1);
println("Array after sorting: " + array);
Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]);

And here is the code for the merge function, although it is obfuscared as I mentioned above:

var merge = function(array, p, q, r) {
    var a = [],
        b = [],
        c = p,
        d, e;
    for (d = 0; c <= q; d++, c++) {
        a[d] = array[c];
    }
    for (e = 0; c <= r; e++, c++) {
        b[e] = array[c];
    }
    c = p;
    for (e = d = 0; d < a.length && e < b.length;) {
        if (a[d] < b[e]) {
            array[c] = a[d];
            d++;
        } else {
            array[c] = b[e];
            e++;
        }
        c++;
    }
    for (; d < a.length;) {
        array[c] = a[d];
        d++;
        c++;
    }
    for (; e < b.length;) {
        array[c] = b[e];
        e++;
        c++;
    }
};

They also require my code inside of the mergeSort function be of the form:

if (____) {
    var ____ = ____;
    mergeSort(____,____,____);
    mergeSort(____,____,____);
    merge(____,____,____,____);
}

Provide the task description and the code for the merge function. — Andrey Mikhaylov - lolmaus
– Andrey Mikhaylov - lolmaus, Commented Nov 21, 2014 at 16:21
merge is a function provided by Khan Academy could you include that function? Is the error coming from your code or theirs? — Matt Burland
– Matt Burland, Commented Nov 21, 2014 at 16:21
Is there a difference between if( r > p ) and if( r - p > 0 )? The only thing I can think of is perhaps there are more cpu operations being performed on r - p > 0 than r > p though I expect r > p would use r - p > 0 as the comparison to tell you whether r > p. — SnowInferno
– SnowInferno, Commented Apr 4, 2015 at 0:28

Oriol · Accepted Answer · 2014-11-21 16:45:10Z

11

Mergesort is a divide and conquer algorithm which splits the range of indices to sort in two, sorts them separately, and then merges the results.

Therefore, middle variable should be the arithmetic mean of from and to, not the half of to.

I have renamed the variables to make it more understandable:

var mergeSort = function(array, from, to) {
    if(to > from) {
        var middle = Math.floor( (from+to)/2 ); // Arithmetic mean
        mergeSort(array, from, middle);
        mergeSort(array, middle+1, to);
        merge(array, from, middle, to);
    }
};

edited Nov 21, 2014 at 16:45

answered Nov 21, 2014 at 16:30

Oriol

291k71 gold badges459 silver badges535 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

georg Over a year ago

I don't think |0 is something a beginner can easily understand. Why not floor?

Oriol Over a year ago

@georg I like |0 to avoid adding more parentheses (and can be faster). But OK, it can confuse beginners, and won't work if the array has more than 2^31 elements. Fixed.

Matt Burland · Accepted Answer · 2014-11-21 16:34:21Z

5

q is supposed to be the half way point between p and r, but you've failed to take into account that the starting point (i.e. p) might not be 0 when you do this:

var q = floor(r/2);

You need to do something like:

var q = floor((r-p)/2) + p;

Although as @Oriol points out the middle point is actually exactly the same as the arithmetic mean and so the calculation can be simplified.

edited Nov 21, 2014 at 16:34

answered Nov 21, 2014 at 16:28

Matt Burland

45.3k18 gold badges110 silver badges182 bronze badges

Comments

Avadhut Thorat · Accepted Answer · 2020-02-08 06:04:31Z

Just for the sake of implementation of the merge sort in JS

function merge(arr){
  if(arr.length <= 1) return arr;
  let mid = Math.floor(arr.length/2);
  let left = merge( arr.slice(0, mid));
  let right = merge(arr.slice(mid))
      function mergeSort(arr1, arr2) {
        let result = [];
        let i=0;
        let j=0;
        while(i< arr1.length && j < arr2.length) {
          if(arr1[i] < arr2[j]){
            result.push(arr1[i])
            i++;
          } else {
            result.push(arr2[j])
            j++;
          }
        }
       while(i < arr1.length) {
          result.push(arr1[i])
          i++;
       }
       while(j < arr2.length){
          result.push(arr2[j])
          j++;
       }    
        return result
    }
  return mergeSort(left,right)
}

console.log(merge([1,4,3,6,2,11,100,44]))

PhiAgent · Accepted Answer · 2021-08-16 20:35:29Z

High level strategy

the merge sort works on the principle that it's better to sort two numbers than to sort a large list of numbers. So what it does is that it breaks down two lists into their individual numbers then compares them one to the other then building the list back up. Given a list of say 1,3,2, it'll split the list into 1 and 3,2 then compare 3 to 2 to get 2,3 and then compare the list of 2,3 to 1. If 1 is less than the first element in list of 2,3 it simply places 1 in front of the list. Just like that, the list of 1,3,2 is sorted into 1,2,3.

pseudocode-steps 1.take first member of first array 2.compare to first member of second array 3.if first member of first array is less than first member of second array 4.put first member into sorted array 5.now merge first array minus first element with second array 6.else take first member of second array merge first array with remaining portion of second array 7.return sorted array

function mergesorted(list1, list2) {
    let sorted = [];
    if (list1.length === 0 || list2.length === 0) {
        return list1.length === 0 ? list2.length === 0 ? [] : list2 : list1;
    }
    if (list1[0] < list2[0]) {
        sorted.push(list1[0])
        return sorted.concat(mergesorted(list1.slice(1), list2))
    } else {
        sorted.push(list2[0])
        return sorted.concat(mergesorted(list1, list2.slice(1)))
    }
}
console.log(mergesorted([1, 2], [3, 4])) //should: [1,2,3,4]
console.log(mergesorted([1,2], [3])) //should: [1,2,3]

coderek · Accepted Answer · 2017-03-10 17:30:01Z

Merge sort implementation, stable and in place

function sort(arr, start, end) {
    if (start >= end-1) return;
    var mid = start + ~~((end-start)/2);
    // after calling this
    // left half and right half are both sorted
    sort(arr, start, mid);
    sort(arr, mid, end);

    /**
     * Now we can do the merging
     */

    // holding merged array
    // size = end-start
    // everything here will be copied back to original array
    var cache = Array(end-start).fill(0);
    var k=mid;
    // this is O(n) to arr[start:end]
    for (var i=start, r=0;i<mid;r++,i++) {
        while (k<end && arr[k] < arr[i]) cache[r++] = arr[k++];
        cache[r] = arr[i];
    }
    // k marks the position of the element in the right half that is bigger than all elements in the left
    // effectively it tells that we should only copy start~start+k element from cache to nums
    // because the rests are the same
    for (var i=0;i<k-start;i++) arr[i+start]=cache[i];
}

Yuniel · Accepted Answer · 2021-03-31 19:57:55Z

1

A nice solution:

const merge = (left, right) => {
  const resArr = [];
  let leftIdx = 0;
  let rightIdx = 0;

  while (leftIdx < left.length && rightIdx < right.length) {
    left[leftIdx] < right[rightIdx]
      ? resArr.push(left[leftIdx++])
      : resArr.push(right[rightIdx++]);
  }
  return [...resArr, ...left.slice(leftIdx), ...right.slice(rightIdx)];
};

const mergeSort = arr =>
  arr.length <= 1
    ? arr
    : merge(
        mergeSort(arr.slice(0, Math.floor(arr.length / 2))),
        mergeSort(arr.slice(Math.floor(arr.length / 2)))
      );

answered Mar 31, 2021 at 19:57

Yuniel

13 bronze badges

Comments

Abanoub Fathy · Accepted Answer · 2021-11-07 21:31:31Z

try this

const mergeTwoSortedArr = (arr1 = [], arr2 = []) => {
    let i = 0,
        j = 0,
        sortedArr = [];

    while(i < arr1.length || j < arr2.length) {
        if(arr1[i] <= arr2[j] || (i < arr1.length && j >= arr2.length)) {
            sortedArr.push(arr1[i]);
            i++;
        }

        if(arr2[j] <= arr1[i] || (j < arr2.length && i >= arr1.length)) {
            sortedArr.push(arr2[j]);
            j++;
        }
    }

    return sortedArr;
}

const mergeSort = (arr) => {
    if(arr.length === 0 || arr.length === 1) {
        return arr;
    }
    
    var mid = Math.floor(arr.length / 2);
    var left = mergeSort(arr.slice(0, mid));
    var right = mergeSort(arr.slice(mid));
    return mergeTwoSortedArr(left, right);
}

when trying this

mergeSort([5, 2, 1, 4])  //[1, 2, 4, 5]

Time Complexity O(nlogn)
logn --> decomposition
n comaprison
Time complexity O(nlogn)

Collectives™ on Stack Overflow

Implementing merge sort in Javascript

7 Answers 7

2 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

2 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related