# Merge Sort in C

## Merge Sort in C#

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 for two merge sorted arrays.

The Following is the outline of the Code Merge Sort Procedure:

```MergeSort(arr[], l,  r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
```

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 + ``" "``);` `            ``}` `        ``}` `    ``}` `}`