javascript merge sort and recursion

Question

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])

Answer 1

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

Answer 2

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.

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]))

Answer 3

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 2ⁿ 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.

Answer 4

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]))

Answer 5

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]));