Merge sort in javascript

Learn what is merge sort and how to implement merge sort algorithm in javascript.

Sorting is one of the most prominent algorithms and building blocks of computer science, we use it more often than any algorithms out there, There is always a race to create a fast sorting algorithm.

List of sorting algorihtms

• Bubble sort algorithm in javascript
• Insertion sort algorithm in javascript
• Selection sort in javascript

Merge sort is one of the fastest sorting algorithm which was invented in 1945 but is still used widely. Having a thorough understanding of it will help you to become a better programmer.

It is a general purpose, comparison-based sort algorithm which uses divide and conquer technique to compare all the data with each other and sort them in the desired order.

It is also a stable sorting algorithm which means it sort repeated elements in the same order that they appear in the input.

Stable sorting algorithms choose one of these, according to the following rule.

If two items compare as equal, then their relative order will be preserved, so that if one came before the other in the input, it will also come before the other in the output.

How merge sort works?

Conceptually merge sorts works as follows:

• Divide the given unsorted elements into n sub element list, each containing only one element (A single element is always sorted).
• Repeatedly merge this sub element lists in the required order until there is only one sub element list. At the end the last list will be the sorted.

Top down merge sort

As in each iteration it first breaks the list into sublist and then sort and merges them, which basically means it is moving from top to down.

Each problem is broken into part, which further breaks into parts until it is easy to solve.

Merging the sorted list

As merge sort uses divide and conquer paradigm to sort the list, merging can be stated as the conquer part.

To merge the sorted sub element list, we compare all the elements of the both the list and then add the elements into temp array in the order.

After comparing and merging both the lists, if there elements left in either of the sub list then we have to add that as well in the temp array and then return this merged list.

const merge = (leftArr, rightArr) => {
  //To merge the both subarrays
  const result = [];
  
  let iL = 0; //To track left sub array
  let iR = 0; //To track right sub array
  
  //Compare the two sub arrays and merge them in the sorted order
  while(iL < leftArr.length && iR < rightArr.length){
    if(leftArr[iL] < rightArr[iR]){
      result.push(leftArr[iL]);
      iL++;
    }else{
      result.push(rightArr[iR]);
      iR++;
    }
  }
  
  //If there are elements in the left sub arrray then add it to the result
  while(iL < leftArr.length){
    result.push(leftArr[iL]);
    iL++;
  }
  
  //If there are elements in the right sub array then add it to the result
  while(iR < rightArr.length){
    result.push(rightArr[iR]);
    iR++;
  }
  
  return result;
}

This merge operation sorts the list in ascending order, if you want to sort in descending order then update it while comparing the elements of the two sub lists leftArr[iL] < rightArr[iR].

As we use a temporary variable to merge the sub lists, the space complexity of merge sort becomes O(N).

---

Dividing the list into sublist for merge sort.

As you can already see in the above image, in each call we divide the list into two sub list till there are only one element and then merge them.

To divide the list we take the mid of the list and create two sublist of half each, that is 0 to Mid and Mid + 1 to end.

Array in javascript has a method called slice(startIndex, endIndex) which returns the shallow copy of the array with given elements between the range of the given indexes.

We will use this to divide the lists and then pass this divided sub lists to merge function for merging them.

const mergeSortRec = (arr) => {
  //Get the length of the array
  const length = arr.length;
  
  //If reached to the bottom then return the array.
  if(length === 1){
    return arr;
  }
  
  //Get the mid of array
  const mid = Math.floor(length / 2);
  //Left sub array
  const left = arr.slice(0, mid);
  //Right sub array
  const right = arr.slice(mid, length);
  
  //Return the sorted and merged right and left sub array
  return merge(mergeSortRec(left), mergeSortRec(right));
}

Complete code of merge sort in javascript

const mergeSortRec = (arr) => {
  //Get the length of the array
  const length = arr.length;
  
  //If reached to the bottom then return the array.
  if(length === 1){
    return arr;
  }
  
  //Get the mid of array
  const mid = Math.floor(length / 2);
  //Left sub array
  const left = arr.slice(0, mid);
  //Right sub array
  const right = arr.slice(mid, length);
  
  //Return the sorted and merged right and left sub array
  return merge(mergeSortRec(left), mergeSortRec(right));
}

const merge = (leftArr, rightArr) => {
  //To merge the both subarrays
  const result = [];
  
  let iL = 0; //To track left sub array
  let iR = 0; //To track right sub array
  
  //Compare the two sub arrays and merge them in the sorted order
  while(iL < leftArr.length && iR < rightArr.length){
    if(leftArr[iL] < rightArr[iR]){
      result.push(leftArr[iL]);
      iL++;
    }else{
      result.push(rightArr[iR]);
      iR++;
    }
  }
  
  //If there are elements in the left sub arrray then add it to the result
  while(iL < leftArr.length){
    result.push(leftArr[iL]);
    iL++;
  }
  
  //If there are elements in the right sub array then add it to the result
  while(iR < rightArr.length){
    result.push(rightArr[iR]);
    iR++;
  }
  
  return result;
}

Input:
console.log(mergeSortRec([10, 7, 8, 9, 1, 5]));
console.log(mergeSortRec([30, 20, 10, 50, 22, 33, 55]));

Output:
[1, 5, 7, 8, 9, 10]
[10, 20, 22, 30, 33, 50, 55]

Time Complexity of merge sort

If you closely monitor the working of merge sort then in each call it breaks the list in the half and then merges it.

So the recurrence relation for it becomes T(n) = 2T(n/2) + n. After solving this we get the result as O(NlogN).

The average and worst case time complexity for merge sort is same, but there is another sorting algorithm whose average case is better than merge sort.

The best case is O(NlogN) typically, but it can be optimized to O(N) for natural variants.

---

Space complexity of merge sort.

For each merge process we use a temporary variable to store the sorted list, so the space complexity is O(N).