Are you sure you are supposed to use recursion for pivoting? This is part of the quick sort algorithm, which indeed, is done recursively. You could make even the pivot recursive, but I don't see why you'd want to. There are several ways of doing this. The most typical actually used by quick sort would proceed like this.
| CODE |
Indecies of two pointers start at two ends of array, excluding pivot.
3 4 1 8 6 5 2 One on the left is > pivot, while right < pivot. Swap.
* ^ ^
3 2 1 8 6 5 4 Left pointer is < pivot, so pointer is advanced. Right > pivot, advanced.
* ^ ^
3 2 1 8 6 5 4 Again, both are correct, so both are advanced.
* ^ ^
3 2 1 8 6 5 4 Left pointer > pivot. Right > pivot. Left stays, right advances.
* ^ ^
3 2 1 8 6 5 4 Pointers merged. Now we need to step back, and swap with pivot.
* ^
3 2 1 8 6 5 4 Perform swap.
^ ^
1 2 3 8 6 5 4 Final state. To do full quick sort, repeat with 1 and 8 as pivots, etc. |
Code for it would look something like this. (C syntax)
| CODE |
a=1;
b=length-1;
while(a!=b)
{
if(array[a]<array[0]){a++; continue;}
if(array[b]>array[0]){b--; continue;}
swap(array+a, array+b);
}
swap(array, array+a-1); |
If you insist on this part being done recursively, you can make it run something along the lines of this.
| CODE |
void pivot(int array[], int a, int b)
{
if(a==b){swap(array, array+a-1);return;}
if(array[a]<array[0]){pivot(array,a+1,b); return;}
if(array[b]>array[0]){pivot(array,a,b-1); return;}
swap(array+a, array+b);
pivot(array,a,b);
}
pivot(array, 1, length-1); |
But honestly, that's just a waste of stack space and jump instructions.
Full quick sort written to implement the first form with recursion would be written like this.
| CODE |
void quicksort(int array[], int length)
{
if(length<=1)return;
a=1;
b=length-1;
while(a!=b)
{
if(array[a]<array[0]){a++; continue;}
if(array[b]>array[0]){b--; continue;}
swap(array+a, array+b);
}
swap(array, array+a-1);
quicksort(array, a-1);
quicksort(array+a,length-a);
} |
This post has been edited by K^2 on Wednesday, Jan 18 2012, 22:51 
