What is Merge Sort?

It is a divide & conquer algorithm that breaks down the given array into smaller sub-arrays until the sub-arrays become so small that they can't be divided further. The algorithm then merges these sub-arrays, in order, to produce a sorted array.

How it works

1. the algo divides the original array into two sub-arrays, a left sub-array, and a right sub-array.
2. recursively sorts these sub-arrays by dividing them into smaller sub-arrays until each sub-array has only one element.
3. merges these sub-arrays in order by comparing the first element of each sub-array and selecting the smallest one until all elements are merged back into the original array.

Runtime & Complexity

Runtime Complexity of O(n log n) (Regardless of the input array's order, Merge Sort has the same time complexity due to its recursive nature and the way it splits and merges the subarrays.)

Space Complexity of O(n). (The space complexity is linear because the total number of elements in the subarrays is equal to the number of elements in the input array.)

This makes it faster than other sorting algorithms, such as insertion sort, selection sort, and bubble sort when working with large data sets.

Implementing the Merge Sort Algorithm in Code

Implementing the Merge Sort algorithm in code involves creating a recursive function that divides the original array into sub-arrays and sorts them. We also need to create a helper function that merges the sorted sub-arrays back into the original array.

1. Create a function named mergeSort that takes an array as an argument and recursively divides the array into left and right sub-arrays.
2. Create a helper function named merge that takes the left and right sub-arrays and merges them back into the original array.
3. Use a for loop to iterate over the elements of the array, and invoke the mergeSort function to sort the elements.
4. In the mergeSort function, use recursion to divide the array into smaller sub-arrays until each sub-array has only one element.