how to modify merge sort to be in place?

Question

I'm looking for an algorithm that modify merge sort to be in place sorting algorithm. I tried to change the indexes instead of splitting the array, but got stuck in the merging fhase.

Answer 1

Iterative merge sort is your friend for O(1) spatial complexity.

Here an implementation with Python:

def merge_sort_in_place(alist):
    i = 1
    while i <= len(alist):
        j = 0
        for j in range(0, len(alist), i * 2):
            left, right = j, min(len(alist), j + 2 * i)
            mid = j + i
            p, q = left, mid
            while p < mid and q < right:
                if alist[p] < alist[q]: # already sorted...
                    p += 1 # ... skip to next pair
                else: # need to swap...
                    temp = alist[q] # store temp value...
                    alist[p + 1: q + 1] = alist[p:q] # ... shift to the right...
                    alist[p] = temp # update value
                    p, mid, q = p + 1, mid + 1, q + 1 # ... go to next pair
        i *= 2
    return alist

Test it out:

import random

big_num = 2**15
l = list(range(big_num))
random.shuffle(l)

assert(merge_sort_in_place(l) == list(range(big_num)))
print("It sorts!")

---

Take [3, 1, 4, 0, 2, 5] for example and see what the inner while loop does when the swap occurs:

We start with: [3, 1, 4, 0, 2, 5]
when: p = 0, q = 1, mid = 1  -->  [1, 3, 4, 0, 2, 5]
when: p = 2, q = 3, mid = 3  -->  [1, 3, 0, 4, 2, 5]
when: p = 0, q = 2, mid = 2  -->  [0, 1, 3, 4, 2, 5]
when: p = 2, q = 4, mid = 4  -->  [0, 1, 2, 3, 4, 5]