For the record, recursion can actually be very elegant. In fact, its actually a better option in some cases.
For example:
Recursive:
public static void recursiveQuicksort(int[] a) {
// shuffle(a); // to guard against worst-case
recursiveQuicksort(a, 0, a.length - 1);
}
// quicksort a[left] to a[right]
public static void recursiveQuicksort(int[] a, int left, int right) {
if (right <= left) return;
int i = partition(a, left, right);
recursiveQuicksort(a, left, i-1);
recursiveQuicksort(a, i+1, right);
}
// partition a[left] to a[right], assumes left < right
private static int partition(int[] a, int left, int right) {
// DK: added check if (left == right):
if (left == right) return left;
int i = left - 1;
int j = right;
while (true) {
while (a[++i] < a[right]) // find item on left to swap
; // a[right] acts as sentinel
while (a[right] < a[--j]) // find item on right to swap
if (j == left) break; // don't go out-of-bounds
if (i >= j) break; // check if pointers cross
swap(a, i, j); // swap two elements into place
}
swap(a, i, right); // swap with partition element
return i;
}
Iterative:
public static void iterativeQuicksort6(int[] a) {
int[] range = new int[a.length+1]; // if (range[i]<0) then skip[i] = |range[i]|
range[0] = a.length-1;
int i, j, sortedCount = 0;
while (sortedCount < a.length) {
for (i=0; i<a.length; i++)
if (range[i] >= i) {
j = range[i];
if (j-i < 7) {
// selectionsort the elements from a[i] to a[j] inclusive
// and set all their ranges to -((j+1)-k)
for (int m=i; m<=j; m++) {
for (int n=m; n>i && a[n-1]>a[n]; n--)
swap(a, n, n-1);
range[m] = -((j+1)-m);
sortedCount++;
}
i = j;
}
else {
for ( ; i<=j; i++) {
int p = partition(a,i,j);
sortedCount++;
if (p > i) range[i] = p-1;
if (p < j) range[p+1] = j;
range[i = p] = -1; // sorted
}
}
}
else {
// skip[i] += skip[i + skip[i]];
while ((j = range[i-range[i]]) < 0) range[i] += j;
i += -range[i]-1;
}
}
}