# Potential quicksort optimizations

I implemented qsort() like this. I was wondering what improvements I could do to make it better.

public static void qsort(int[] a, int start, int end) {
if (start >= end) return;
int pivot = start;
int lt = start + 1;
int gt = end;
int temp;
while (lt <= gt) {
if (a[pivot] > a[lt]) {
temp = a[pivot];
a[pivot] = a[lt];
a[lt] = temp;
pivot = lt++;
} else {
while (gt >= lt)  {
if (a[gt] < a[lt]) {
temp = a[lt];
a[lt] = a[gt];
a[gt] = temp;
break;
}
gt--;
}
gt--;
}
}
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);
}


One thing I quickly spot is this:
If your second while loop completes naturally instead of via a break, you will also exit the first while loop. Thus the last instruction executed, gt--, is unnecessary.

Let's look at the execution paths:

//BEGINLOOPS
while (lt <= gt) {
if (a[pivot] > a[lt]) {
temp = a[pivot];
a[pivot] = a[lt];
a[lt] = temp;
pivot = lt++;
} else {
while (gt >= lt)  {//If false, does gt--;, then jumps to ENDLOOPS
if (a[gt] < a[lt]) {
temp = a[lt];
a[lt] = a[gt];
a[gt] = temp;
break;//does gt--;, then jumps to BEGINLOOPS
}
gt--;
}
gt--;
}
}
//ENDLOOPS
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);


There's only 2 ways the second while loop can end. Either via a break or via gt decrementing until it equalizes with lt.

So we should alter the one execution path where the gt--; is unnecessary.

//BEGINLOOPS
while (lt <= gt) {
if (a[pivot] > a[lt]) {
temp = a[pivot];
a[pivot] = a[lt];
a[lt] = temp;
pivot = lt++;
} else {
while (gt >= lt)  {//If false, jumps to ENDLOOPS
if (a[gt] < a[lt]) {
temp = a[lt];
a[lt] = a[gt];
a[gt] = temp;
gt--;//does gt--;,
break;//then jumps to BEGINLOOPS
}
gt--;
}
}
}
//ENDLOOPS
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);


That saves you one instruction for each time you end via that one execution path.

Additionally, you know what pivot is already, so I'd split this in a helper function and a recursive function.

public static void quickSort(int[] a, int start, int end) {
if (start >= end) return;
qsort(a, start, end);
}

private static void qsort(int[] a, int start, int end) {
int pivot = start;
int lt = start + 1;
int gt = end;
int temp;
while (lt <= gt) {
if (a[pivot] > a[lt]) {
temp = a[pivot];
a[pivot] = a[lt];
a[lt] = temp;
pivot = lt++;
} else {
while (gt >= lt)  {
if (a[gt] < a[lt]) {
temp = a[lt];
a[lt] = a[gt];
a[gt] = temp;
gt--;
break;
}
gt--;
}
}
}
pivot--;
if(start < pivot){
qsort(a, start, pivot);
}
if(lt < end){
qsort(a, lt, end);
}
}


Whoa, that's different near the end. Yeah, I rushed ahead. Let me explain.

pivot starts at start. lt starts at start + 1, which is pivot + 1. Furthermore, there's only one place where pivot is changed (pivot = lt++) and there's only one place where lt is changed (also pivot = lt++). Looking at that line tells us it does this:
Set pivot to the value of lt (which by definition is pivot + 1), then up lt by one, making lt to be pivot + 1 again. One wonders whether you even need the different variable - if you wanted to conserve memory, I would strip the unneeded variable.

So with that logic, excepting the moment of which that one line is executed in which they are altered, pivot and lt are always 1 apart. Thus I can use lt as a shorthand for pivot + 1.

Examples, with pivot = 12:

qsort(a, start, pivot - 1);//12 - 1 = 11
qsort(a, pivot + 1, end);//12 + 1 = 13

pivot--;//lt is still 13, 12-- = 11
if(start < pivot){//only run if start >= end is false, so only run if start < end is true.
qsort(a, start, pivot);//11
}
if(lt < end){//only run if start < end is true.
qsort(a, lt, end);//lt is still 13, I changed nothing to it.
}


You should also consider removing the pivot variable and seeing if that makes a difference.

That said, all performance optimizations should be profiled and benchmarked properly. Who knows what optimizations the JVM will make for you. But if you were a human who executed the code by hand, these optimizations would speed the code up for you.

Looking deeper at it (why not?) shows me one more problem: if you made no swaps, you will still split around your pivot, reiterating the entire array except one element. That's really, really bad. You'll basically have $T_{end-start}$ iterations, where $T$ is a triangular number. In other words: 100 elements sorted gives you 5050 iterations or so. That's bad.
Let's add a boolean for that.

public static void quickSort(int[] a, int start, int end) {
if (start >= end) return;
qsort(a, start, end);
}

private static void qsort(int[] a, int start, int end) {
int pivot = start;
int lt = start + 1;
int gt = end;
int temp;
boolean swapped = false;
while (lt <= gt) {
if (a[pivot] > a[lt]) {
temp = a[pivot];
a[pivot] = a[lt];
a[lt] = temp;
pivot = lt++;
swapped = true;
} else {
while (gt >= lt)  {
if (a[gt] < a[lt]) {
temp = a[lt];
a[lt] = a[gt];
a[gt] = temp;
swapped = true;
gt--;
break;
}
gt--;
}
}
}
if(swapped){
pivot--;
if(start < pivot){
qsort(a, start, pivot);
}
if(lt < end){
qsort(a, lt, end);
}
}
}