Quick Sort
(gamedev.net/...)
is a pretty sorting algorithm,
invented back in 1962 by professor C.A.R. Hoare
(...infcharles.html).
 It sorts inside the array itself,
using only a couple of pointers that work outside in.
 It uses powerful recursion to split, split and split the series of numbers
(...sortieren/quick...).
 It is quite fast.
Step taken 
<=4 
to do 
>4 
4 as pivot 

5, 3, 4, 2, 1


1 and 5 swapped 
1 
3, 4, 2 
5 
3, 4, and 2 to left 
1, 3, 4, 2 

5 
3 as pivot 
<=3 
to do 
>3 

5 
1 and 3 to left 
1, 3 
4, 2 


5 
4 and 2 swapped 
1, 3, 2 

4 

5 
3 as pivot 
<=3 
to do 
>3 

4 

5 

1, 3, 2 


4 

5 
1, 3, 2 to left? 
1, 3, 2 



4 

5 
Yet, I have never been able to understand how Quick Sort can work on the array {1, 3, 2}, having '3' as pivot.
 All numbers in the array are <=3.
 The pivot number remains 3 in deeper recursions.
 The recursion never ends, never produces any result.
Alternative
An elegant alternative:
Step taken 
<=4 
to do 
>=4 
4 as pivot 

5, 3, 4, 2, 1


1 and 5 swapped 
1 
3, 4, 2 
5 
3 to left 
1, 3 
4, 2 
5 
2 and 4 swapped 
1, 3, 2 

4, 5 
3 as pivot 
<=3 
to do 
>=3 

4, 5 
1 to left 
1 
3, 2 


4, 5 
3 and 2 swapped 
1, 2 

3 

4, 5 
 Smaller numbers still move left.
 Larger numbers still move right.
 But all equal numbers
are candidate for a swap.
So, the numbers that
equal the pivot,
can move both left and right.
That seems odd and indecisive, resulting in inefficiency.
But on the contrary, it
speeds up
the sorting because
 it splits series into parts of more equal size,
 it swaps more numbers into the right direction per recursion,
 which makes the recursion less deep.
Till
next week, with a
demo of this alternative Quicksort algorithm
Nut
