In Place Merge Sort

In place merge sort is a merge sort variant that tries to keep the extra memory small. Standard merge sort uses an auxiliary array of size $n$ during merging. In place merge sort instead merges two adjacent sorted ranges inside the original array.

The main difficulty is the merge step. Splitting is easy, but merging two sorted adjacent ranges without a large buffer is more complex and usually slower.

Problem

Given an array $A$ of length $n$, reorder it such that:

while using less than $O(n)$ auxiliary memory.

Idea

The array is divided recursively as in ordinary merge sort. After both halves are sorted, the algorithm merges them by shifting elements inside the same array.

If the next element in the left half is already less than or equal to the next element in the right half, keep it in place. Otherwise, take the smaller right element and insert it before the current left element by shifting the intervening elements one position to the right.

Algorithm

in_place_merge_sort(A, l, r):
    if l >= r:
        return

    mid = (l + r) // 2

    in_place_merge_sort(A, l, mid)
    in_place_merge_sort(A, mid + 1, r)

    in_place_merge(A, l, mid, r)

in_place_merge(A, l, mid, r):
    i = l
    j = mid + 1

    while i <= mid and j <= r:
        if A[i] <= A[j]:
            i += 1
        else:
            value = A[j]
            k = j

            while k > i:
                A[k] = A[k - 1]
                k -= 1

            A[i] = value

            i += 1
            mid += 1
            j += 1

Example

Let:

The two sorted halves are:

Merge in place:

Final array:

Correctness

The recursive calls sort the left and right halves. During merging, the prefix before index $i$ is always sorted and contains the smallest elements seen so far. When $A[i] \le A[j]$, keeping $A[i]$ preserves that invariant. When $A[j] < A[i]$, shifting and inserting $A[j]$ at position $i$ places the smallest remaining element next. The invariant continues until one side is exhausted, so the whole range becomes sorted.

Complexity

This simple shifting version has the same recursive split structure as merge sort, but the merge step can take quadratic time in the size of the merged range.

Properties

Notes

There are advanced in place merging algorithms with better asymptotic behavior, but they are substantially harder to implement. Many production systems prefer a small buffer or a full auxiliary array because the code is simpler and faster in practice.

This page describes the basic stable in place version. It is useful for understanding the tradeoff between memory and merge cost.

Implementation

def in_place_merge_sort(a):
    def sort(l, r):
        if l >= r:
            return

        mid = (l + r) // 2
        sort(l, mid)
        sort(mid + 1, r)
        merge(l, mid, r)

    def merge(l, mid, r):
        i = l
        j = mid + 1

        while i <= mid and j <= r:
            if a[i] <= a[j]:
                i += 1
            else:
                value = a[j]
                k = j

                while k > i:
                    a[k] = a[k - 1]
                    k -= 1

                a[i] = value

                i += 1
                mid += 1
                j += 1

    sort(0, len(a) - 1)
    return a

func InPlaceMergeSort(a []int) {
	var sort func(int, int)

	sort = func(l, r int) {
		if l >= r {
			return
		}

		mid := (l + r) / 2
		sort(l, mid)
		sort(mid+1, r)
		inPlaceMerge(a, l, mid, r)
	}

	sort(0, len(a)-1)
}

func inPlaceMerge(a []int, l, mid, r int) {
	i := l
	j := mid + 1

	for i <= mid && j <= r {
		if a[i] <= a[j] {
			i++
		} else {
			value := a[j]
			k := j

			for k > i {
				a[k] = a[k-1]
				k--
			}

			a[i] = value

			i++
			mid++
			j++
		}
	}
}