To demonstrate that even non-tail recursive methods can be expressed in a non-recursive way, here is the quick sort that way:
public class NonRecursiveQuickSort<E> {
// injected final fields and constructor deleted from print
private static class Stack {
final int begin;
final int fin;
public Stack(int begin, int fin) {
this.begin = begin;
this.fin = fin;
}
}
public void qsort(SortableCollection<E> sortable, int start, int end) {
final List<Stack> stack = new LinkedList<>();
final Partitioner<E> partitioner = new Partitioner<>(comparator, swapper);
stack.add(new Stack(start, end));
int i = 1;
while (!stack.isEmpty()) {
Stack iter = stack.remove(0);
if (iter.begin < iter.fin) {
final E pivot = sortable.get(iter.begin);
int cutIndex = partitioner.partition(sortable, iter.begin, iter.fin, pivot);
if( cutIndex == iter.begin ){
cutIndex++;
}
stack.add(new Stack(iter.begin, cutIndex - 1));
stack.add(new Stack(cutIndex, iter.fin));
}
}
}
}
This code implements a stack on the Java level. While it sees that there is still something scheduled to be sorted in stack, it fetched it from the stack and does the sort partitioning, and schedules the two parts for being sorted.
This code is more complex than the previous one and you have to understand the role of the Stack class and how it works. On the other hand, the program uses only one instance of the Partitioner class and it is also possible to use a thread pool to schedule the subsequent sorts instead of handling the tasks in a single process. This may speed up the sort when it is executed on a multi-CPU machine. However, this is a bit more complex task and this chapter contains a lot of new things without multitasking; therefore, we will look at multithread code in two chapters later only.
Additionally, find some architectural reason why not to put this modification into the method partition. That method could just return large+1 in case large == start.