If you are given 4 red sticks of different heights placed from lower to higher height order and 4 green sticks of different heights placed from lower to higher height order. Task is to arrange red and green sticks together from lower to higher height..
A basic way to do this is to pick smallest by comparing smaller sticks of red and green and place it. Next pick 2nd highest stick. Continue this till all sticks are placed in correct order. In Merge sort this basic technique of merging to sorted array is used.
Logic:
Merge sort uses a concept of ‘divide and conquer‘ to sort elements.
a. Divide given elements in half, continue dividing elements unless there is only one element present to sort. As one element is always a sorted element, return and start next step.
b. Merge two elements together in a sorted order. continue merging two sorted sub arrays till all input elements are in sorted order.
Example:
Consider input elements as 4,2,8,1,6,3
Dividing action is performed by calling MergeSort function recursively, in each call mid of array is calculated and two subarrays are formed like input[start to mid] and input[mid+1 to end] and sorting and merging two subarrays is performed by calling Merge function recursively.
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 |
private void MergeSort(int[] input, int start, int end) { if (start < end) { int e = (start + end) / 2; MergeSort(input, start, e); MergeSort(input, e + 1, end); Merge(input, start, e, end); } } private void Merge(int[] input, int start, int middle, int end) { int[] output = new int[end - start + 1]; int p = start; int q = middle + 1; int r = 0; while (p <= middle && q <= end) { if (input[p] < input[q]) { output[r++] = input[p++]; } else { output[r++] = input[q++]; } } while (p <= (middle)) { output[r++] = input[p++]; } while (q <= end) { output[r++] = input[q++]; } int k = 0; int i = start; while (k < output.Length && i <= end) { input[i++] = output[k++]; } } |
Analysis:
Calculating mid of array takes constant time regardless of size of the array . So time complexity of this operation is O(1).
When we combine two sorted array , each element is checked so time complexity for this operation is O(n)
In each step array is divided in half and sort two subarrays of size n/2. So the total time complexity of sorting n elements can be expressed as following :
T(n) = T(n/2) + T(n/2) + O(n) :: T(n)=2T(n/2) + O(n)
By using Master theorem, Time complexity is O(nlog n)
Merge sort uses an extra space to hold two halves so his sort is not a in place sort and space complexity is O(n).