Tail recursive sort

Question

I've heard of this implementation of quick sort (in pseudocode):

TAIL-RECURSIVE-QUICKSORT(A, p, r)
 while p < r
 q = PARTITION(A, p, r)
 if q < (p + (r-p)/2)
 TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
 p = q+1
 else
 TAIL-RECURSIVE-QUICKSORT(A, q+1, p)
 r = q-1

Here it is partially implemented.

private static void quickSort(int[] arr, int lo, int hi){
 if(lo >= hi) return;
 int p = partition(arr, lo, hi);
 // modified to choose small partition first
 if((p - lo )<=(hi-p)){
 System.out.println(String.format("Sorting left first %d %d %d",lo,p,hi)) ;
 quickSort(arr, lo, p);
 quickSort(arr, p+1, hi);
 }else {
 System.out.println(String.format("Sorting right first %d %d %d",lo,p,hi));
 quickSort(arr, p+1, hi);
 quickSort(arr, lo, p);
 }
}

Can it be made any faster? FWIW I profiled the above code against regular (recursive) quicksort and it was usually faster (tested on randomly generated arrays).

screenshot
(full size)

Here is partition and a method for swapping

private static int partition(int[] a, int p, int r) {
 int x = a[p];
 int i = p-1 ;
 int j = r+1 ;
 while (true) {
 i++;
 while ( i< r && a[i] < x)
 i++;
 j--;
 while (j>p && a[j] > x)
 j--;
 if (i < j)
 swap(a, i, j);
 else
 return j;
 }
}
private static void swap(int[] a, int i, int j) {
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}

• 200_success: Java just doesn't do tail-call optimization, period. Not even when the code is structured to be tail-call friendly.
• 200_success: Your implementation doesn't match the pseudocode.
• Celeritas: @200_success that's what I wast trying to explain, the pseudocode has a bug in it, but my code doesn't (so that's why it doesn't match).

Answer 1

private static void quickSort(int[] arr, int lo, int hi){

Spell variable names out! There is nothing gained with abbreviating variable names, especially so short ones, it only makes the code harder to read.

---

int p = partition(arr, lo, hi);

Same here.

---

System.out.println(String.format("Sorting left first %d %d %d",lo,p,hi)) ;

Here is one simple rule:

Whenever you want to interact with the screen, may it be printing to the console or redrawing any graphical element, it is going to be expensive.

You want to profile your code without these printlns.

---

private static int partition(int[] a, int p, int r) {

Same here. I know that it is mostly done this way, but code is easier to read when you gave stuff actual names. Example?

while (j>p && a[j] > x)
 j--;

Quick, what does this code do?

---

int x = a[p];

x is a bad variable name for one simple reason, x is a dimension. You should avoid using x, y and z as names unless you're dealing with dimensions.

---

private static void swap(int[] a, int i, int j) {
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}

Same here, long variable names would make this make it better to read by a long shot.