Sort Two Parts Sorted

Problem Overview

The array is made of two parts that are each already sorted, so sorting from scratch throws that order away.

Intuition

The array is made of two parts that are each already sorted, so sorting from scratch throws that order away. The first place where a value is smaller than the one before it marks where the second part begins. From there, this is the merge step of merge sort. Only one part needs a spare copy, so copying the shorter one keeps the extra memory small. The direction of the merge decides which part must be copied: filling from the front is safe when the left part is in the buffer, and filling from the back is safe when the right part is.

Algorithm

1Scan forward while each value is at least the one before it. The index where this stops is mid, the start of the second part.
2If the scan reached the end, the array is already sorted, so return.
3If the left part is no longer than the right, copy it into a buffer. Merge the buffer with the right part from the front, writing at index 0 upward, and finish by copying any leftover buffer values.
4Otherwise copy the right part into a buffer. Merge the left part with the buffer from the back, writing at the last index downward, and finish by copying any leftover buffer values.
5Leftover values still sitting in the array are already in their final places, so they need no copy.

Example Walkthrough

Input: arr = [2,3,8,-1,7,10]

1. The order drops between 8 and -1, so the parts are 2, 3, 8 and -1, 7, 10.
2. Both parts have length 3, so the left part goes into the buffer and the merge runs from the front.
3. Picking the smaller head each time writes -1, 2, 3, 7, and 8. The value 10 is already in the last slot.

Output: [-1,2,3,7,8,10]

Common Pitfalls

• Calling a full sort ignores the two sorted parts and costs n log n time instead of linear time.
• Merging from the front with the right part in the buffer can overwrite left values before they are read. Match the merge direction to the copied part.
• Use a strict drop to find the split. Equal neighbors belong to the same sorted part.
• If there is no drop at all, return early rather than merging an empty part.

Sort Two Parts Sorted.java

Java

// Approach: The array is two sorted runs. Find the first index where the
// order drops; with no drop it is already sorted. Copy only the shorter run
// into a buffer and merge back in place. If the left run is shorter, merge
// from the front; otherwise merge from the back. Either way the write
// position never passes an unread value of the run left in the array.
// Complexity: O(n) time, O(min(left, right)) extra space.
class Solution {
    public void mergeTwoParts(int[] arr) {
        int n = arr.length;
        int mid = 1;
        while (mid < n && arr[mid - 1] <= arr[mid])
            mid++;
        if (mid >= n)
            return;

        if (mid <= n - mid) {
            int[] left = new int[mid];
            System.arraycopy(arr, 0, left, 0, mid);
            int i = 0, j = mid, k = 0;
            while (i < mid && j < n)
                arr[k++] = left[i] <= arr[j] ? left[i++] : arr[j++];
            while (i < mid)
                arr[k++] = left[i++];
        } else {
            int len = n - mid;
            int[] right = new int[len];
            System.arraycopy(arr, mid, right, 0, len);
            int i = mid - 1, j = len - 1, k = n - 1;
            while (i >= 0 && j >= 0)
                arr[k--] = arr[i] > right[j] ? arr[i--] : right[j--];
            while (j >= 0)
                arr[k--] = right[j--];
        }
    }
}

Was this solution helpful?