non necusive quicksort

qsort.cpp

#include <climits>
#include <cassert>
#include <utility>

/*
** The following quicksort implementation avoids recursion by
** using an explicit stack.  Furthermore, by always pushing onto
** the stack the larger portion of the problem, and looping on
** the smaller portion, we ensure that we don't need a very large
** stack.
**
** This code is based on http://alienryderflex.com/quicksort/
*/

template< class Array, class Int >
void bengoldberg1::qsort( Array array, Int elements ) {
  enum { max_size = CHAR_BIT * sizeof(Int) };
  pair< Int, Int > stack[ max_size ];
  Int L = 0, R = elements-1;
  unsigned int i = 0;
  do {
    while( L < R ) {
      Int Linit = L, Rinit = R;
      auto pivot = std::move(array[L]);
      do {
        while( array[R] >= pivot ) if( --R <= L ) goto done;
        array[ L++ ] = std::move(array[R]);
        if( L >= R ) goto done;
        while ( array[L] <= pivot ) if( ++L >= R ) goto done;
        array[ R-- ] = std::move(array[L]);
      } while( L < R );
      done:
      assert( L == R );
      array[ L ] = std::move(pivot);
      
      Int Lsize = L - Linit, Rsize = Rinit - R;
      if( Lsize > Rsize ) {
        stack[i++] = std::make_pair( Linit, L-1 );
        L = L + 1;
        R = Rinit;
      } else {
        stack[i++] = std::make_pair( R+1, Rinit );
        L = Linit;
        R = R + 1;
      }
    }
    if( i == 0 ) return;
    std::tie( L, R ) = stack[--i];
  } while( 1 );
}