Introduction

Working Procedure

Do refer the code available the end of this section to understand the following theory.

1. Consider an array,arr of n elements. Let left be the starting index and right be the ending index.
2. Merge Sort:
   1. Recursion calls will be made if there exist more than one element in the array.
   2. Find the mid point of the array, mid=(left+right)/2.
   3. Make the first recursive call from left to mid.
   4. Make the second recursive call from mid+1 to right.
   5. Now merge this array from index left to right using merge function.
3. Merge Function:
   1. Let i=left be the start index for left subarray, j=mid+1 be the start index for right subarray and k=left be the start index for temporary array.
   2. Loop until i<=left and r<=right(That is either of the subarray is looped completely).
   1. If arr[i] is lesser than arr[j](if the current element in left subarray is lesser than current element in right subarray) then copy arr[i] to temp[k] and increment i, k.
   2. Else copy arr[j] to temp[k] and increment j, k.
   3. Copy the remaining elements of left subarray to temporary array(if there are any).
   4. Copy the remaining elements of right subarray to temporary array(if there are any).
   5. Finally copy the elements from temporary array to our required array(temp->arr).

Time Complexity

PS: We give random inputs because the no. of input will generally be 100 or 1000 to find the time complexity and manually giving so many inputs is cumbersome work.

There exists two recursive calls in which the elements gets halved in each call. And the transfer of elements from arr->temp and at last from temp->arr will effect the time complexity. So declare a global variable count, increment this variable in all the loops present in the merge function (within the loops at step 3.2, 3.3, 3.4 & 3.5 in the above working procedure).

Time Complexity: O(nlog(n))