Merge Sort:

This is a Divide and Conquer algorithm. It divides the input collection into two portions, recursively calls itself for the two divided portions, and then merges the two sorted portions. This is one of the most efficient algorithms. Merge Sort Algorithm works in three parts:

1. Divide: At first, it divides the given collection of elements into two equal halves and then recursively passes these halves to itself.
2. Sorting: Unless, there is only one element left in each half, the division continues, after that, those two end elements (leaf nodes) are sorted.
3. Merging: Finally, the sorted arrays from the top step are merged in order to form the sorted collection of elements

The working of the merge sort algorithm is simulated in below-mentioned figure:

Here's the pseudocode:

1procedure mergesort( var a as array )
2   if ( n == 1 ) return a
3   var l1 as array = a[0] ... a[n/2]
4   var l2 as array = a[n/2+1] ... a[n]
5   l1 = mergesort( l1 )
6   l2 = mergesort( l2 )
7   return merge( l1, l2 )
8end procedure
9
10procedure merge( var a as array, var b as array )
11   var c as array
12   while ( a and b have elements )
13      if ( a[0] > b[0] )
14         add b[0] to the end of c
15         remove b[0] from b
16      else
17         add a[0] to the end of c
18         remove a[0] from a
19      end if
20   end while
21   
22   while ( a has elements )
23      add a[0] to the end of c
24      remove a[0] from a
25   end while
26   
27
28
29   while ( b has elements )
30      add b[0] to the end of c
31      remove b[0] from b
32   end while
33   
34   return c
35end procedure

Time Complexity: O(NlogN)

Space Complexity: O(N)

Best Suited Scenario:

The merge sort algorithm is best suited with most of the data structures and the given collection is in completely unsorted order. This algorithm is feasible for a very large number of data set and this is likely due to its time complexity.

xxxxxxxxxx

console.log(mergeSort([5, 4, 3, 2, 1]));

function merge(leftArr, rightArr) {

  let resultArray = [], leftIndex = 0, rightIndex = 0;

​

  // Sort parts

  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {

    if (leftArr[leftIndex] < rightArr[rightIndex]) {

      resultArray.push(leftArr[leftIndex]);

      leftIndex++; // move left array cursor

    } else {

      resultArray.push(rightArr[rightIndex]);

      rightIndex++; // move right array cursor

    }

  }

​

  // There will be one element remaining from either left or the right

  // Concat to account for it

  return resultArray

          .concat(leftArr.slice(leftIndex))

          .concat(rightArr.slice(rightIndex));

}

​

function mergeSort(unsortedArr) {

  // Only one element base case

  if (unsortedArr.length <= 1) {

    return unsortedArr;

  }

​

  // Determine midpoint

  const midIdx = Math.floor(unsortedArr.length / 2);