Get high-quality organic groceries delivered to you regularly with Quickllly Subscription Box. Choose your favorite grocery products, select the frequency of your order and enjoy your choice of organic Indian groceries at home. Click here to know more!

In this week’s newsletter I want to introduce you to Merge Sort algorithm, and demonstrate how to implement a Merge Sort algorithm with an implementation in C#

What is Merge Sort?

Merge Sort is an efficient sorting algorithm that falls under the Divide and Conquer set of algorithms.

It is similar to Quick Sort, which can help efficiently sort a given set of elements in required order.

The algorithm takes a constant O(NlogN) time for all cases, which makes it a bit more efficient than Quick Sort, which sometimes falls above O(NlogN) in worst cases.

Implementing Merge Sort - Algorithm

Implementing Merge Sort is similar to Quick Sort, except that the Merge Sort divides the given input set into pieces as small as individual elements, and then recursively merges these partitioned pieces - while placing the elements in these subsets into proper order.

The algorithm works in four simple steps:

1. For a given input set of elements A consisting of N elements, place two pointers left and right which represent the opposites of the set. Compute the Midpoint mid such that mid = (left + right) / 2

2. Partition the set into two subsets AL[left...mid] and AR[mid+1...right]

3. recursively apply Step 1 and Step 2 on these two subsets AL and AR with left, mid and mid+1, right as the new pointers. This is repeated till the left and right pointers overlap (meaning the subsets now contain individual elements).

4. Merge the new created subsets AL and AR into the actual set A such that the elements from AL and AR are sorted in order.

Time Complexity

While Merge Sort is an efficient sorting algorithm, it takes logarithmic time to sort a given set of elements. Hence its time complexity is O(NLogN). However, implementing the algorithm also requires a temporary buffer to place the elements, hence it also has a space complexity of O(N).

You can check out the full article here - https://referbruv.com/blog/understanding-merge-sort-comparison-and-analysis/

I hope you’d find this article informative and useful.

See you next week!

Udemy Holi Sale Alert: Grab highly rated Online courses starting from ₹449.