Listing 4 Non-Recursive Quicksort

/* Quick sort routine (not recursive) */

/* Prototypes */
void QuickSort( int *List, int Begin, int End );
void ShellSort( int *List, int Begin, int End );

#define MAXSTACK 200
int Stack[MAXSTACK];
int StackPoint;

void
QuickSort( int *List, int Begin, int End )
{
       int Value, Tmp, i, j;

       StackPoint = 2;
       do
       {
              /* Divide the list in two */
              Value = List[End];
              i = Begin - 1;
              j = End;
              do {
                     while( List[++i] < Value );
                     while( List[--j] > Value );
                     Tmp = List[i];
                     List[i] = List[j];
                     List[j] = Tmp;
              } while( j > i );
              List[j] = List[i];
              List[i] = List[End];
              List[End] = Tmp;
              /* If more than 2 items push the first part */
              if( i - Begin > 2 )
              {
                     if( StackPoint >= MAXSTACK )
                            ShellSort( List, Begin, i-1 );
                     else
                     {
                            Stack[StackPoint++] = i-1;
                            Stack[StackPoint++] = Begin;
                     }
              }
                     if( End - i > 2)
                     {
                            if( StackPoint >= MAXSTACK )
                                   ShellSort( List, i+1, End );
                            else
                            {
                                   Stack[StackPoint++] = End;
                                   Stack[StackPoint++] = i+1;
                            }
                     }
                     Begin = Stack[--StackPoint];
                     End = Stack[--StackPoint];
              } while( StackPoint );
       }

       /* Shell sort for when the stack is full */
       void
       ShellSort( int *List, int Begin, int End )
       {
              int i, j, Mid, Value;

              for( Mid = 1; Mid <= End - Begin + 1; )
                     Mid = 3 * Mid + 1;
              do {
                     Mid /= 3;
                     for( i=Mid+1; i <= End - Begin + 1; i++ )
                     {
                            Value = List[Begin+i];
                            j = i;
                            while(j > Mid
                            && List[Begin+j-Mid] > Value )
                            {
                            List[Begin+j] = List[Begin+j-Mid];
                            j = j - Mid;
                            }
                     List[Begin+j] = Value;
                     }
       } while( Mid != 1 );
}