arrays - How to sort in-place using the merge sort algorithm? -

i know question not specific.

all want tell me how convert normal merge sort in-place merge sort (or merge sort constant space overhead).

all can find (on net) pages saying "it complex" or "out of scope of text".

the known ways merge in-place (without space) complex reduced practical program. (taken from here)

even if complex, what basic concept of how make merge sort in-place?

knuth left exercise (vol 3, 5.2.5). there exists in-place merge sort. must implemented carefully.

first, naive in-place merge such described here isn't right solution. downgrades performance o(n²).

the idea sort part of array while using rest working area merging.

for example following merge function.

void wmerge(key* xs, int i, int m, int j, int n, int w) {     while (i < m && j < n)         swap(xs, w++, xs[i] < xs[j] ? i++ : j++);     while (i < m)         swap(xs, w++, i++);     while (j < n)         swap(xs, w++, j++); }   

it takes array xs, 2 sorted sub arrays represented range [i, m) , [j, n) respectively. working area starts w. compare standard merge algorithm given in textbooks, 1 exchanges contents between sorted sub array , working area. result, previous working area contains merged sorted elements, while previous elements stored in working area moved 2 sub arrays.

however, there 2 constrains must satisfied:

1. the work area should within bound of array. in other words, should big enough hold elements exchanged in without causing out-of-bound error;
2. the work area can overlapped either of 2 sorted arrays, however, should ensured there not unmerged elements being overwritten;

with merging algorithm defined, it's easy imagine solution, can sort half of array; next question is, how deal rest of unsort part stored in work area shown below:

... unsorted 1/2 array ... | ... sorted 1/2 array ... 

one intuitive idea recursive sort half of working area, there 1/4 elements haven't been sorted yet.

... unsorted 1/4 array ... | sorted 1/4 array b | sorted 1/2 array ... 

the key point @ stage must merge sorted 1/4 elements b sorted 1/2 elements sooner or later.

is working area left, holds 1/4 elements, big enough merge , b? unfortunately, isn't.

however, second constraint mentioned above gives hint, can exploit arranging working area overlap either sub array if can ensure merging sequence unmerged elements won't overwritten.

actually, instead of sorting second half of working area, can sort first half, , put working area between 2 sorted arrays this:

... sorted 1/4 array b | unsorted work area | ... sorted 1/2 array ... 

this setup effects arrange work area overlap sub array a. idea proposed in [jyrki katajainen, tomi pasanen, jukka teuhola. ``practical in-place mergesort''. nordic journal of computing, 1996].

so thing left repeat above step, reduce working area 1/2,, 1/4, 1/8 ..., when working area becomes small enough, example, 2 elements left, can switch trivial insertion sort end algorithm.

here implementation in ansi c based on paper.

void imsort(key* xs, int l, int u);  void swap(key* xs, int i, int j) {     key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp; }  /*   * sort xs[l, u), , put result working area w.   * constraint, len(w) == u - l  */ void wsort(key* xs, int l, int u, int w) {     int m;     if (u - l > 1) {         m = l + (u - l) / 2;         imsort(xs, l, m);         imsort(xs, m, u);         wmerge(xs, l, m, m, u, w);     }     else         while (l < u)             swap(xs, l++, w++); }  void imsort(key* xs, int l, int u) {     int m, n, w;     if (u - l > 1) {         m = l + (u - l) / 2;         w = l + u - m;         wsort(xs, l, m, w); /* last half contains sorted elements */         while (w - l > 2) {             n = w;             w = l + (n - l + 1) / 2;             wsort(xs, w, n, l);  /* first half of previous working area contains sorted elements */             wmerge(xs, l, l + n - w, n, u, w);         }         (n = w; n > l; --n) /*switch insertion sort*/             (m = n; m < u && xs[m] < xs[m-1]; ++m)                 swap(xs, m, m - 1);     } } 

where wmerge defined previously.

the full source code can found here , detailed explanation can found here

by way, version isn't fastest merge sort because needs more swap operations. according test, it's faster standard version, allocates spaces in every recursion. it's slower optimized version, doubles original array in advance, , uses further merging.