4

I am trying to understand how JavaScript merge sort function work. And I struggle understanding how the recursive function work. This is the code:

const mergeSort = array => {
  if (array.length < 2) {
    //function stop here
    return array
  }

  const middle = Math.floor(array.length / 2);
  const leftSide = array.slice(0, middle);
  const rightSide = array.slice(middle, array.length);
  return merge(mergeSort(leftSide), mergeSort(rightSide))

};

const merge = (left, right) => {
  const result = [];

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift);
    }
  }

  while(left.length) result.push(left.shift());

  while(right.length) result.push(right.shift());

  return result;
}
mergeSort([5,3,8,10,4,1])
7
  • 1
    Note that all values are either local to the current function call or are parameters passed to it. So after [5] and [3, 8] are sorted, the return merge... line calls merge with [5] and [3, 8], which returns [3, 5, 8]. Something similar happens in the right half: [10] is returned, [4, 1] is sorted to [1, 4] and then [10] and [1, 4] are merged into [1, 4, 10]. Finally [3, 5, 8] and [1, 4, 10] is merged into [1, 3, 4, 5, 8, 10]. Each recursive call keeps its own copy of the local variables along the way. Feb 18, 2020 at 19:34
  • 1
    write this out on some paper: you start with [5, 3, 8, 10, 4, 1], that gets split in mergeSort into two arrays. Both those arrays are (recursively) passed into mergeSort again, where [5, 3, 8] becomes [5] and [3, 8]. For [5] we're done, and it gets returned as is. For [3,8], we again recurse, and they end up returend as [3] and [8]. Those get merged: what happens during the merge step? Write it out: it's an important exercise if you want to understand any algorithm. Feb 18, 2020 at 19:36
  • 1
    but merge first is called like that merge(3, 8), then executes but the function itself cannot keep these values, then it executes again with 5 but I dont get how 5 is passed it cannot be merge([3,8,5]) because mergeSort returns only one value...
    – shane_00
    Feb 18, 2020 at 19:41
  • 1
    Hey Mike, does the splitting hapening inside merge function or merge gets called only with a single parameter?
    – shane_00
    Feb 18, 2020 at 19:43
  • @shaunaa - merge is being called with two parameters, each parameter is an array, and merge returns a single merged array. This is a very inefficient way to implement merge sort. It would be better to do a one time allocation of a second array, then merge back and forth between the two arrays, passing arrays and indexes as parameters.
    – rcgldr
    Feb 18, 2020 at 22:46

5 Answers 5

5

To understand recursion you can trace all recursion levels with indentation. For example:

const mergeSort = (array, level) => {
  logWithLevel(level, "Start sort array " + array);
  if(array.length < 2) {
    //function stop here
    logWithLevel(level, "Finish sort array " + array);
    return array;
  }

  const middle = Math.floor(array.length / 2);
  logWithLevel(level, "middle element is " + array[middle])
  const leftSide = array.slice(0, middle);
  const rightSide = array.slice(middle, array.length);
  var result = merge(mergeSort(leftSide, level + 1), mergeSort(rightSide, level + 1));
  logWithLevel(level, "Finish sort array " + result);
  return result;
};

const merge = (left, right) => {
  const result = [];

  while(left.length && right.length){
    if(left[0] <= right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }

  while(left.length) result.push(left.shift());

  while(right.length) result.push(right.shift());

  return result;
}

const logWithLevel = (level, data) => {
    var s = ""
    for (i = 0; i < level; i++) {
        s += "    ";
    }
    console.log(s + data);
}

And result:

> mergeSort([5,3,8,10,4,1], 0)
    Start sort array 5,3,8,10,4,1
    middle element is 10
        Start sort array 5,3,8
        middle element is 3
            Start sort array 5
            Finish sort array 5
            Start sort array 3,8
            middle element is 8
                Start sort array 3
                Finish sort array 3
                Start sort array 8
                Finish sort array 8
            Finish sort array 3,8
        Finish sort array 3,5,8
        Start sort array 10,4,1
        middle element is 4
            Start sort array 10
            Finish sort array 10
            Start sort array 4,1
            middle element is 1
                Start sort array 4
                Finish sort array 4
                Start sort array 1
                Finish sort array 1
            Finish sort array 1,4
        Finish sort array 1,4,10
    Finish sort array 1,3,4,5,8,10
2

Recursion is like a loop, but different.
A loop iterates until an end condition;
recursion 'calls itself' until a base case.
Loops iterate like a story from beginning to end;
recursion is like a story where each chapter is enclosed in the previous chapter... until you get to the innermost chapter (the base case). Only after reading this innermost chapter can you finally understand clearly what is happening. So now you can back up one chapter and re-read it, and understand that chapter. As you go on understanding and backing-up the hierarchy of chapters, you finally reach the start of the story and have finished (understanding) the book.


In this example, the base case is array.length < 2: an array with one or zero elements. Any array of one/zero elements is by definition already sorted.
After breaking the array down like this, we ask: "what small work can I contribute to ensure — as we recombine the array — that it will be recombined in a sorted order?" In this example that work is the merge function.

mergeSort divides the array-argument and calls itself until the array has been completely divided into one-element arrays. It calls itself here:

return merge( mergeSort(leftSide), mergeSort(rightSide))

This line of code is added to the call stack, but to evaluate merge, mergeSort must be evaluated first. So mergeSort is added to the call stack, and run. But each time it runs, there is another return of merge(). This results in the call stack piling up with calls to merge. We cannot begin to go back up the call stack and evaluate merge() until we stop calling it: when the base case is finally met. Now we begin to 'back out of our story', starting with the innermost chapter, and going back up the call stack.

As we go back up the stack, we contribute work in the form of the merge function: We compare the first elements of the leftSide and rightSide and sort them. Whichever side is less than the other gets pushed into the result and that side gets shifted (replaced) by the next element.

Why does this work?
This algorithm ensures that even if the smallest element is initially last (or the biggest element is first), they will be sorted, even though the work done is only comparing two characters each step. By breaking down the array (and piling up the call stack) in this way, we ensure that merge will always be called enough times, so that the smallest number will always 'get to the front of the queue' at each step, and there will be 'enough steps' that it will come out first.

In the GeekForGeeks image of Mohammed's answer, check the path of the number 3. It is 'worked on' by the merge function 3 times. Each time it 'gets to the front of the queue': the first time the queue is only of two (elements in length), the second time the queue is of 4 and the third time the queue is of 7 (or 8). Even if 3 had been initially last (and the example array had been a length of 8) it would still only have been 'worked on' three times and would still have got to the front of the queue. You may realise that for any array of length upto 2n that n steps of work (comparisons) are needed on the smallest element (or by extension: on each element ) to bring it to the front of the queue (or by extension: the sorted position ), no matter where it starts in the array.

1

Merge Sort work on the principle of divide and conquer. Here a problem divided into a smaller subproblem and it continues till the problem is solvable. Then we solve the bigger by combining smaller solved problems.

In merge sort, we are dividing the array into smaller array's till it's size is 1 and an array of size 1 is already sorted. After this, we are merging the smaller array such a way that the newly created array is also sorted.

In the diagram you can see in the fourth level all the subarray are of size 1 and from there onward we are merging the subArray.

enter image description here image Source: GeekForGeeks

function mergeSort(input) {
  const {length:arraySize} = input;
  if (arraySize < 2) return input;
  const mid = Math.floor(arraySize/2);
  const sortedLeftArray = mergeSort(input.slice(0,mid));
  const sortedRightArray = mergeSort(input.slice(mid, arraySize));
  return merge(sortedLeftArray, sortedRightArray);
}

function merge (left, right){
  let result = []
  while(left.length && right.length){
    if(left[0]< right[0]){
      result.push(left.shift())
    }else{
      result.push(right.shift())
    }
  }
  /* Either left/right array will be empty or both */
  return [...result, ...left, ...right];
}

console.log(mergeSort([5,3,8,10,4,1]))

2
  • 4
    The OP is looking for an explanation of code, not more code with no explanation... Jun 16, 2020 at 14:41
  • 2
    Although this code might solve the problem, a good answer should explain what the code does and how it helps
    – BDL
    Sep 4, 2020 at 8:22
0

Recursion can be a tricky thing. The best way to look at it is; I'm creating one function that will extend into itself with a different portion of the original data that was passed into it. When some condition has been reached, these extensions pull upwards (using return) into itself, reconnecting the current branch of the recursive tree into its parent branch, and finally resolving at the original tree node itself. To keep up with this analogy going forward, consider thinking of array as a branch.

For merge sort, your goal is to split your array in half, and extend into each of these new arrays to do the same until only one item is left in the current array. When only 1 item exists, you've reached the condition in which you pull back (return) and unite your arrays! Now this return is just the start, you've told this path along the tree that it's time to unite. What comes next is the logic on what to do with this data as it's pulled back into the original tree node.

Lets get to the code:

function mergeSort(array) {
  if (array.length == 1) { // when you have one item left, return to the previous branch
    return array
  } else { // otherwise
    var half = Math.floor(array.length/2) // get a halfway point for your array
    var left_branch = mergeSort(array.slice(0,array.length-half)) // split the first half into the left branch
    var right_branch = mergeSort(array.slice(0-half)) // and the right half into the right branch
    return // do something with your branches as you pull back ...
  }
}

So far, we're telling our code to keep splitting our current array in half until its length is 1. Now when our left and right array have both reached one, they will pull back into their origin, which happens to be our else statement where they were defined.

Now we sort our data as it returns back to its origins. You compare the size of each item in the left and right array and return them as a single array in that order. Be careful! Not all branches were created equal and your path descending from one side may have more or fewer branches from the other! Make sure to account for a comparison of something like Array(5) against Array(4).

At this point, I hope you understand recursion! All that's left is the main part of your merge sort, the comparison of two arrays. Here's my method

var lb_i = 0 // left branch iterator
var rb_i = 0 // right branch iterator
return array.map(v => // loop over the original unsorted array at this branch (how it appeared before the recursive split) and set to a new sorted value
  !right_branch[rb_i] || left_branch[lb_i] < right_branch[rb_i]
  // if right branch is undefined, get your data from the left
  // otherwise, check which branch item is smaller at its current iterator
  // (if the left branch is undefined, the comparison will always be false)
    ? left_branch[lb_i++] // insert from the left branch, then increase the iterator
    : right_branch[rb_i++] // insert from the right branch, then increase the iterator
)

Note: This comparison logic is likely JavaScript specific due to how it handles logic on undefined variables

A test case: (My entry on free code camp, don't cheat!!)

function mergeSort(array) {
  if (array.length == 1) {
    return array
  } else {
    var mid = Math.floor(array.length/2)
    var lh = mergeSort(array.slice(0,array.length-mid))
    var rh = mergeSort(array.slice(0-mid))
    var lh_i = 0
    var rh_i = 0
    return array.map(v => 
      !rh[rh_i] || lh[lh_i] < rh[rh_i]
        ? lh[lh_i++]
        : rh[rh_i++]
    )
  }
}
console.log(mergeSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]))

-1
Sorting with recursive

function sort(arr){
const staticArr = [...arr]
  function recMaxSort(arrayARG,maxEL=0,resultArr = []){
    const [firstEl,...rest] = arrayARG;
    if (staticArr.length === resultArr.length){
      return resultArr
    }
    if (!firstEl){
      resultArr=[maxEL,...resultArr]
      const newArray = staticArr.filter(el=>{return !resultArr.includes(el)})
      return recMaxSort(newArray,0,resultArr)
    }

    if (maxEL>firstEl){
      return recMaxSort(rest,maxEL,resultArr)
    } else if (firstEl>=maxEL){
      return recMaxSort(rest,firstEl,resultArr)
    }

  }

  return  recMaxSort(arr)

}

 
 console.log(sort([231,4,7,3,54,500]));

3
  • 1
    Can you please add some explaination?
    – dan1st
    Sep 4, 2020 at 7:29
  • @dan1st Hello ! What exactly you don't understand ?My function based on array destructuring. When recursion goes on it compare all values from array.
    – Quintis
    Sep 5, 2020 at 15:33
  • I just wrote that because I got your answer in the LQP Review Queue and you just wrote code and did not explain it.
    – dan1st
    Sep 5, 2020 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.