Merge Sort In-Place

• The standard implementation of merge sort requires an extra temporary array for the merge operation to be performed in linear time. 
• We can avoid this extra space by effectively performing the merge sort in-place. But this would require us to move the elements within the original array.
• The recursive calls of the merge sort implementation remain the same. The change is required only in the logic of merge procedure.
• The idea behind this approach is to mark the starting and ending of the subarrays using two pointers, say start and end. Then iterate through both these subarrays simultaneously and in each iteration, we place the smaller of the two elements (present in each subarray) at its correct position in the sorted array.
• Placing the element at the correct position may require shifting the later elements one step towards the right.
• In this way, we can sort the array in-place using merge sort.

Algorithm for Merge Sort:

• Let the recursive function be mergeSortHelper(array, left, right) which takes the given array, starting position of the subarray, and ending position of the subarray, respectively as its arguments.
• Initially, we call the function as mergeSortHelper(arr, 0, N-1).
• Base Condition: If left >= right, return.
• We divide the array into two parts: arr[left, mid] and arr[mid +1, right], where mid = (left + right) / 2.
• Recursively call the function on both the subarrays:
  • mergeSortHelper(arr, left, mid)
  • mergeSortHelper(arr, mid + 1, right)
• Now, merge the two sorted subarrays by calling the merge function as merge(arr, left, mid, right). Here we do not pass the starting position of the second subarray, as it can be derived from the ending position of the first subarray.

Algorithm for Merge:

• Let the function be merge(array, start, mid, end), which takes the array, starting position of the first sorted subarray, ending position of the first sorted subarray, and ending position of the second sorted subarray, respectively, as its arguments.
• Let start2 be the starting position of the second subarray, where start2 = mid + 1.
• If arr[mid] <= arr[start2], then the complete arr[start, end] is already sorted, so we can skip the merge procedure and just return.
• Repeat the following steps until start <= mid AND start2 <= end:
  • If arr[start] <= arr[start2]: then the element in the first subarray is the smaller one, and it is placed at the correct position. So, just increment start by one.
  • Otherwise, the element in the second subarray is the smaller one. So, we need to place it at its correct position i.e. at index start.
    • Store a copy of arr[start2] in a temporary variable say, temp.
    • Now, shift all the elements from position start + 1 to start2 - 1, one step towards the right.
    • Place the element at its correct position, i.e., arr[start] = temp.
    • Increment the pointers start, mid, and start2 by one.

O(N^2*log(N)), where N is the number of elements in the array.

In the worst case, there are O(log(N)) recursive calls. For every recursive call, we merge two sorted arrays. Merge operation requires O(N) time for iterating over the subarrays, for each iteration we shift the array one step towards the right, which requires O(N) time. So in the worst case, the merge operation will take O(N^2) time. Hence, the overall time complexity is O(N^2 * log(N)) which is greater than the standard implementation.

O(log(N)), where N is the number of elements in the array.

Extra space is required for the recursion stack. Since there are O(log(N)) recursive calls. Hence, overall space complexity is O(log(N)), which is very less.