# Tail recursive sort

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).

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;
}

• Java just doesn't do tail-call optimization, period. Not even when the code is structured to be tail-call friendly. Commented Aug 22, 2014 at 22:50
• Your implementation doesn't match the pseudocode. Commented Aug 22, 2014 at 23:01
• @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). Commented Aug 22, 2014 at 23:16

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.