## Reinvent wheels, my quick sort implementation, just for fun

Not deeply optimized.
The depth of the recursion is restricted , because the recursion is only performed for the partition with less element. Even under the worst case, the stack depth will still be under control.
Tail recursion is eliminated.

Brief explanation:

 12345678910111213141516171819202122232425262728293031323334353637 initial state: p<<<                                      # p===                                      # |                                         p>>> p...                                      | |-----------------------------------------| ..........................................# state after choosing the pivot: p<<<                                      # p===                                      # |                                         p>>> |p...                                     | ||----------------------------------------| =.........................................# the middle state during partitioning: p<<<                                      # |        p===                             # |        |                          p>>>  # |        |         p...             |     # |--------|---------|----------------|-----# <<<<<<<<<==========.................>>>>>># the final state after partition: p<<<                                      # |               p===                      # |               |               p>>>      # |               |               p...      # |---------------|---------------|---------# <<<<<<<<<<<<<<<<================>>>>>>>>>># Then, recurse.

Pointer “p<<<" points to the begining of the "<<<" area in which each element is preceding to the pivot. Pointer "p===" points to the begining of the "===" area in which each element is equivalent to the pivot. Pointer "p>>>” points to the begining of the “>>>” area in which each element is succeeding to the pivot.
Pointer “p…” points to the begining of the “…” area in which each element is unprocessed.

The code:

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 template class QuickSort { public:     static void sort(Elem pp[], size_t n) {         Elem *pe, *pu, *ps;         // pp:"p<<<", pe:"p===", ps:"p>>>", pu:"p..."         do {             // recursion exit, use other sort algorithm to process small array             // recommendation: use sorting network algorithm when array size less than 9             if(n < Cutoff) {                 ShortSort::sort(pp, n);                 return;             }             pe = pp;             pu = pp;             ps = pp+n;             // choosing pivot             swap(pe, pivot(pp, n));             pu++;             // partitioning             while(pu < ps) {                 while((*pe == *pu) && (pu < ps)) ++pu;                 while((*pe < *pu) && (pu < ps)) {                     --ps;                     swap(pu, ps);                 }                 while((*pu < *pe) && (pu < ps)) {                     swap(pe, pu);                     ++pe;                     ++pu;                 }             }             // recursion only for the partition with less elements             if((pe - pp) < (n - (ps - pp))) {                 sort(pp, pe - pp);                 n = n - (ps - pp);                 pp = ps;             } else {                 sort(ps, n - (ps - pp));                 n = pe - pp;             }             // tail recursion elimination         } while(true);     } private:     static Elem *pivot(Elem pp[], size_t n) {         if(n < 10) return pp + n/2;         else return pp + random(n);         // random(n) should return a uniformly distributed random number in [0, n)     } };