Hope you read my previous article on the selection sort, and how it is similar to Insertion sort.
If not, check out this article below.
We will see the Merge Sort today.
Merge Sort is a divide and conquer sorting algorithms, which uses recursion to sort.
Here is a pictorial representation of how it works.
(Top -> Bottom)
In the above diagram, we are dissecting the elements of array based on a pivot value (depending on the length of the array).
Since the dissection happens back to back due to recursion, we would need a base condition. Here our base condition is to return the input if the "input.length" is less than or equal to 1.
Once the elements are dissected, the sorting happens.
Here we compare the values of 2 arrays dissected starting from the index "0". If the value on the left found to be smaller, we will push that element to the result array and increment the counter on the left array (only), same goes to the array on right.
We do it repeatedly until the counter value reaches the array length.
In the end, there will be one element either in right or the left array which needs to be pushed to the result (the largest element), so we concatenate that value while returning the result.
Video reference (Start from 3:08)
Here is the result.
Hope you find this helpful.
Please share your feedback, will see you again.