In this article, I will be taking you through one of the sorting algorithms, Merge sort, step by step and perform a complete analysis of it.
In this sorting algorithm, we use the idea of divide and conquer. We divide the array into two parts, sort them and merge them to get the elements in ascending or descending order.
This sorting is done using recursion. We take an array and keep diving from the middle till we get only one element in each halves. Then we sort the arrays and merge them back.
Let’s take an example to give you a clearer idea:
(source: wikipedia)

Algorithm

• If there is only one element in the list, it’s already sorted
• Divide the array into two halves until it cannot be divided
• Merge the smaller list to new list which is sorted

Output

On executing the above code, you will obtain the below output.

Time complexity

For an array of n elements, order of merge sort is f(n)=O(nlog2n).

References

This site uses Akismet to reduce spam. Learn how your comment data is processed.