Merge Sort – Data Structures and Algorithms using C#

Merge sort is an efficient sorting algorithm that uses a divide-and-conquer approach to sort a given set of elements. It works by recursively splitting list into several sub-lists until each sub-list consists of a single element and merging those sub-lists in a manner that results into a sorted list..

For example, an array of 8 elements would be split in the middle in the 2 arrays of 4 items. The splitting continues until each split array has only 1 element in it. Since the array now has 1 element in it, that split array is known to be sorted. Now at this point, the arrays are reconstructed, but the values are put back together in sort array. And after each reconstruction, the sorted array doubles in size and this continue until the array is all reconstructed and fully sorted.

Merge Sort

 

C# Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Program
{
        static void Main(string[] args)
        {
            int[] arr = { 5, 12, 4, 32, 67, 23, 9, 14, 99, 21 };
 
            // call the function MergeSort
            var sortedArr = MergeSort(arr, 0, arr.Length - 1);
 
            // print the sorted array
            Console.WriteLine("Sorted Array: ");
            for (int i = 0; i < sortedArr.Length; i++)
            {
                Console.Write(sortedArr[i] + " ");
            }
 
            Console.ReadKey();
        }
 
        private static int[] MergeSort(int[] array, int start, int end)
        {
            if (start < end)
            {
                int middle = (end + start) / 2;
                int[] leftArr = MergeSort(array, start, middle);
                int[] rightArr = MergeSort(array, middle + 1, end);
                int[] mergedArr = Merge(leftArr, rightArr);
                return mergedArr;
            }
            return new int[] { array[start] };
        }
        private static int[] Merge(int[] leftArr, int[] rightArr)
        {
            int[] mergedArr = new int[leftArr.Length + rightArr.Length];
 
            int leftIndex = 0;
            int rightIndex = 0;
            int mergedIndex = 0;
 
            // Traverse both arrays simultaneously and 
            // store the smallest element of both to mergedArr
            while (leftIndex < leftArr.Length && rightIndex < rightArr.Length)
            {
                if (leftArr[leftIndex] < rightArr[rightIndex])
                {
                    mergedArr[mergedIndex++] = leftArr[leftIndex++];
                }
                else
                {
                    mergedArr[mergedIndex++] = rightArr[rightIndex++];
                }
            }
 
            // If any elements remain in the left array, append them to mergedArr
            while (leftIndex < leftArr.Length)
            {
                mergedArr[mergedIndex++] = leftArr[leftIndex++];
            }
 
            // If any elements remain in the right array, append them to mergedArr
            while (rightIndex < rightArr.Length)
            {
                mergedArr[mergedIndex++] = rightArr[rightIndex++];
            }
 
            return mergedArr;
        }
}
Complexity of Merge Sort

Worst case performance: O(n log n)

In worst case, only nlogn comparisons and swaps are needed. This is substantially less than n^2 that we are seeing at bubble and insertion sort. And this makes merge sort a reasonable candidate for large unsorted data sets.

Average case performance: O(n log n)

The average case is also nlogn and appropriate for large data sets.

Best case performance: O(n log n)

The average case is also nlogn. There is no performance improvement in best cases because merge sort has to perform its data splitting, all the comparisons and the reconstruction the same way regardless of if the data is already sorted or not.

Space complexity: O(n)

Merge sort requires auxiliary array for merge operation. Therefore, space complexity is O(n). These extra allocations increase the memory head, and they also have some other effects like the heap can become populated,and more garbage collections can be occurring, and there’s all kinds of things can happen because of this. So when you’re looking at merge sort as a candidate algorithm, you really have to take care of this.

 
So, it was all about Merge Sorting Algorithm, if you have any query then please comment below and let us know. If you liked this article, then please follow us on Facebook to get notification for new posts.

Happy Learning 🙂

Rahul is a Data Geek, technology enthusiast, a passionate writer, thinker with passion for computer programming.  He loves to explore technology and finds ultimate joy when writing about trending technology, geek stuff and web development.