Merge Sort Algorithm with C# Program code

Merge sort is a sorting algorithm which is based on Divide-and-conquer paradigm. The algorithm divides the array in two halves in each step and recursively calls itself on the two halves. And then merges two sorted halves. The mergeArray() function is used to merge two sorted arrays.

Following is outline of Merge Sort Procedure:

Time Complexity: Time complexity of Merge Sort in all three cases (Average, Worst and Best) is O(nlogn).
Auxiliary Space: O(n). Used by temp array used in mergeArray() procedure.

C# Code for Merge Sort
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MergeSort
{
    class MergeSortArray
    {
        /* Procedure for merging two sorted array.
        *Note that both array are part of single array. arr1[start.....mid] and arr2[mid+1 ... end]*/
        void mergeArray(int[] arr, int start, int mid, int end)
        {
            /* Create a temporary array for stroing merged array (Length of temp array will be
             * sum of size of both array to be merged)*/
            int[] temp = new int[end - start + 1];
            int i = start, j = mid+1, k=0;
            // Now traverse both array simultaniously and store the smallest element of both to temp array
            while (i <= mid && j <= end)
            {
                if (arr[i] < arr[j])
                {
                    temp[k] = arr[i];
                    k++;
                    i++;
                }
                else
                {
                    temp[k] = arr[j];
                    k++;
                    j++;
                }
            }
            // If there is any element remain in first array then add it to temp array
            while(i<=mid)
            {
                temp[k] = arr[i];
                k++;
                i++;
            }
            // If any element remain in second array then add it to temp array
            while (j <= end)
            {
                temp[k] = arr[j];
                k++;
                j++;
            }
            // Now temp has merged sorted element of both array
            // Traverse temp array and store element of temp array to original array
            k=0;
            i=start;
            while (k < temp.Length && i <= end)
            {
                arr[i] = temp[k];
                i++;
                k++;
            }
        }
        // Recursive Merge Procedure
        void mergesort(int[] arr, int start, int end)
        {
            if (start < end)
            {
                int mid = (end + start) / 2;
                mergesort(arr, start, mid);
                mergesort(arr, mid + 1, end);
                mergeArray(arr, start, mid, end);
            }
        }
        // Main driver function
        static void Main(string[] args)
        {
            int[] arr = {5,9,2,3,6,4,11,10,8,14 }; // this is the array to be sorted
            MergeSortArray merge = new MergeSortArray();
            
            // Calling Merge Procedure
            merge.mergesort(arr, 0, arr.Length-1);
            // Printing Sorted array. after merge sort
            foreach (int a in arr)
            {
                Console.Write(a + " ");
            }
        }
    }
}

READ  Do You Really Have What it Takes to Become a Freelance Writer?

Leave a Reply

Your email address will not be published. Required fields are marked *