A beautiful in place - merge algorithm. Test it on inverted arrays to understand how rotations work. Fastest known in place stable sort. No risk of exploding a stack. Cost: a relatively high number of moves. Stack can still be expensive too. This is a merge sort with a smart in place merge that 'rotates' the sub arrays. This code is litteraly copied from the C++ stl library and translated in Java.
class InPlaceStableSort extends AlgoTri {
InPlaceStableSort (int t, VueTris v) { super("InPlaceStable",
t, v); }
int lower (int from, int to, int val) {
int len = to - from, half;
while (len > 0) {
half = len/2;
int mid= from + half;
if (compare (mid, val) < 0) {
from = mid+1;
len = len - half -1;
} else len = half;
}
return from;
}
int upper (int from, int to, int val) {
int len = to - from, half;
while (len > 0) {
half = len/2;
int mid= from + half;
if (compare (val, mid) < 0)
len = half;
else {
from = mid+1;
len = len - half -1;
}
}
return from;
}
void insert_sort (int from, int to) {
delay (ext); // emulates recursion's & stack cost
if (to > from+1) {
for (int i = from+1; i < to; i++) {
for (int j = i; j > from; j--) {
if (compare(j, j-1)<0)
exchange(j, j-1);
else break;
}
}
}
}
int gcd (int m, int n) {
while (n!=0) { int t = m % n; m=n; n=t; }
return m;
}
void reverse (int from, int to) {
while (from < to) {
exchange(from++, to--);
}
}
void rotate (int from, int mid, int to) {
/* a less sophisticated but costlier version:
reverse(from, mid-1);
reverse(mid, to-1);
reverse(from, to-1);
*/
if (from==mid || mid==to) return;
int n = gcd(to - from, mid - from);
while (n-- != 0) {
int val = item(from+n);
int shift = mid - from;
int p1 = from+n, p2=from+n+shift;
while (p2 != from + n) {
assign(p1, item(p2));
p1=p2;
if ( to - p2 > shift) p2 += shift;
else p2=from + (shift - (to - p2));
}
assign(p1, val);
}
}
void merge(int from, int pivot, int to, int len1, int len2)
{
delay(ext);
if (len1 == 0 || len2==0) return;
if (len1+len2 == 2) {
if (compare(pivot, from) < 0)
exchange(pivot, from);
return;
}
int first_cut, second_cut;
int len11, len22;
if (len1 > len2) {
len11=len1/2;
first_cut = from + len11;
second_cut = lower(pivot, to, first_cut);
len22 = second_cut - pivot;
} else {
len22 = len2/2;
second_cut = pivot + len22;
first_cut = upper(from, pivot, second_cut);
len11=first_cut - from;
}
rotate(first_cut, pivot, second_cut);
int new_mid=first_cut+len22;
merge(from, first_cut, new_mid, len11, len22);
merge(new_mid, second_cut, to, len1 - len11, len2 - len22);
}
void sort(int from, int to) {
delay (ext); // emulates recursion's & stack cost
if (to - from < 12) {
insert_sort (from, to);
return;
}
int middle = (from + to)/2;
sort (from, middle);
sort (middle, to);
merge(from, middle, to, middle-from, to - middle);
}
public void sort () {
sort(0, size);
}
};