Merge Sort Algorithm In C#

Introduction

In this article, I will be discussing Merge sort algorithm. Merge sort is a comparison based sorting algorithm based on the divide and conquer approach.

The input array will be divided into subarrays and those subarrays will be further divided until each subarray contains a single element. Then, these subarrays will be merged together to get a single sorted array.

This algorithm is asked frequently in job interviews.So first, I am going to explain Merge sort algorithm. Then, I will be providing a C# code to execute it.

The Merge Sort Algorithm

This algorithm works as follows.

Divide the unsorted array of size N into N subarrays having single element each.
Take two adjacent subarrays and merge them to form a sorted subarray having 2 elements.Now we have N/2 subarrays of size 2.
Repeat the process until a single sorted array is obtained.

Let us understand this with the help of an example.

Let us take input array as – 9 8 5 7 3 1

The sorted output for this array is – 1 3 5 7 8 9

As evident from the diagram below, at each step, the array of size N is being divided into 2 subarrays of size N/2 until no further division is possible.

Step 1

At first step, the array is divided into 2 subarrays (9 8 5) and (7 3 1) of size 3 each.The subarray (9 8 5) is further divided into subarrays(9 8) and (5).The subarray (9 8) is further divided into (9) and (8). Since no further division is possible so division process will stop.Similarly, the subarray (7 3 1) from will be divided into subarrays (7 3) and (1).The subarray (7 3) is further divided into (7) and (3) and then the division process will stop.

Step 2

Since all subarrays now contain one element each, the merge process will start.Subarrays (9) and (8) will merge in sorted order to form subarray(8 9), subarrays (7) and (3) will merge to form sorted subarray (3 7). Subarrays(8 9) and (5) will merge to form sorted array (5 8 9), subarrays (3 7) and (1) will merge to form sorted array (1 3 7).Finally, subarrays (5 8 9) and (1 3 7) will merge to produce the final sorted array (1 3 5 7 8 9).

Fig :- Pictorial representation of Merge Sort algorithm

Time Complexity

Merge sort is a recursive algorithm.The array of size N is divided into the maximum of logN parts, and the merging of all subarrays into a single array takes O(N) time. Hence in all the three cases (worst, average, best), the time complexity of Merge sort is O(NLogN).