Sorting Algorithm Examples

This is a collection of programs implementing a wide variety of sorting algorithms. The code has been optimized for speed instead of readability. You will find them to perform better than the perspective standard algorithms. The Combo Sort should be suitable for production usages.

These examples were constructed by studying the following text books:

• Robert Sedgewick, "Algorithms in C"
• Mark Allen Weiss, "Data Structures and Algorithm Analysis"
• Tenenbaum, Langsam, Augenstein, "Data Structures Using C"

Some short descriptions on each of the algorithms:

Exchange two adjacent elements if they are out of order. Repeat until array is sorted. This is a slow algorithm.

 

#include
#include

#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);
 
void ArraySort(int This[], CMPFUN fun_ptr, uint32 ub)
{
  /* bubble sort */

  uint32 indx;
  uint32 indx2;
  int temp;
  int temp2;
  int flipped;

  if (ub <= 1)
    return;

  indx = 1;
  do
  {
    flipped = 0;
    for (indx2 = ub - 1; indx2 >= indx; --indx2)
    {
      temp = This[indx2];
      temp2 = This[indx2 - 1];
      if ((*fun_ptr)(temp2, temp) > 0)
      {
        This[indx2 - 1] = temp;
        This[indx2] = temp2;
        flipped = 1;
      }
    }
  } while ((++indx < ub) && flipped);
}

#define ARRAY_SIZE 14

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    my_array[indx] = rand();
  }
  /* my_array[ARRAY_SIZE - 1] = ARRAY_SIZE / 3; */
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;
  int indx2;

  for (indx2 = 0; indx2 < 80000; ++indx2)
  {
    fill_array();
    ArraySort(my_array, cmpfun, ARRAY_SIZE);
    for (indx=1; indx < ARRAY_SIZE; ++indx)
    {
      if (my_array[indx - 1] > my_array[indx])
      {
        printf("bad sort\n");
        return(1);
      }
    }
  }

  return(0);
}

 

 

Find the largest element in the array, and put it in the proper place. Repeat until array is sorted. This is also slow.

#include
#include


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);




void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* selection sort */

  uint32 indx;
  uint32 indx2;
  uint32 large_pos;
  int temp;
  int large;

  if (the_len <= 1)
    return;

  for (indx = the_len - 1; indx > 0; --indx)
  {
    /* find the largest number, then put it at the end of the array */
    large = This[0];
    large_pos = 0;

    for (indx2 = 1; indx2 <= indx; ++indx2)
    {
      temp = This[indx2];
      if ((*fun_ptr)(temp ,large) > 0)
      {
        large = temp;
        large_pos = indx2;
      }
    }
    This[large_pos] = This[indx];
    This[indx] = large;
  }
}

#define ARRAY_SIZE 14

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    my_array[indx] = rand();
  }
  /* my_array[ARRAY_SIZE - 1] = ARRAY_SIZE / 3; */
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;
  int indx2;

  for (indx2 = 0; indx2 < 80000; ++indx2)
  {
    fill_array();
    ArraySort(my_array, cmpfun, ARRAY_SIZE);
    for (indx=1; indx < ARRAY_SIZE; ++indx)
    {
      if (my_array[indx - 1] > my_array[indx])
      {
        printf("bad sort\n");
        return(1);
      }
    }
  }

  return(0);
}

Scan successive elements for out of order item, then insert the item in the proper place. Sort small array fast, big array very slowly.

#include
#include


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);



void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* insertion sort */

  uint32 indx;
  int cur_val;
  int prev_val;

  if (the_len <= 1)
    return;

  prev_val = This[0];

  for (indx = 1; indx < the_len; ++indx)
  {
    cur_val = This[indx];
    if ((*fun_ptr)(prev_val, cur_val) > 0)
    {
      /* out of order: array[indx-1] > array[indx] */
      uint32 indx2;
      This[indx] = prev_val; /* move up the larger item first */

      /* find the insertion point for the smaller item */
      for (indx2 = indx - 1; indx2 > 0;)
      {
        int temp_val = This[indx2 - 1];
        if ((*fun_ptr)(temp_val, cur_val) > 0)
        {
          This[indx2--] = temp_val;
          /* still out of order, move up 1 slot to make room */
        }
        else
          break;
      }
      This[indx2] = cur_val; /* insert the smaller item right here */
    }
    else
    {
      /* in order, advance to next element */
      prev_val = cur_val;
    }
  }
}

#define ARRAY_SIZE 14

int my_array[ARRAY_SIZE];

uint32 fill_array()
{
  int indx;
  uint32 checksum = 0;
  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    checksum += my_array[indx] = rand();
  }
  return checksum;
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;
  int indx2;
  uint32 checksum1;
  uint32 checksum2;

  for (indx2 = 0; indx2 < 80000; ++indx2)
  {
    checksum1 = fill_array();
    ArraySort(my_array, cmpfun, ARRAY_SIZE);
    for (indx=1; indx < ARRAY_SIZE; ++indx)
    {
      if (my_array[indx - 1] > my_array[indx])
      {
        printf("bad sort\n");
        return(1);
      }
    }
    checksum2 = 0;
    for (indx=0; indx < ARRAY_SIZE; ++indx)
    {
      checksum2 += my_array[indx];
    }
    if (checksum1 != checksum2)
    {
      printf("bad checksum %d %d\n", checksum1, checksum2);
    }
  }

  return(0);
}

Partition array into two segments. The first segment all elements are less than or equal to the pivot value. The second segment all elements are greater or equal to the pivot value. Sort the two segments recursively. Quicksort is fastest on average, but sometimes unbalanced partitions can lead to very slow sorting.

 

#include
#include

#define INSERTION_SORT_BOUND 16 /* boundary point to use insertion sort */

#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);

/* explain function
* Description:
*   fixarray::Qsort() is an internal subroutine that implements quick sort.
*
* Return Value: none
*/
void Qsort(int This[], CMPFUN fun_ptr, uint32 first, uint32 last)
{
  uint32 stack_pointer = 0;
  int first_stack[32];
  int last_stack[32];

  for (;;)
  {
    if (last - first <= INSERTION_SORT_BOUND)
    {
      /* for small sort, use insertion sort */
      uint32 indx;
      int prev_val = This[first];
      int cur_val;

      for (indx = first + 1; indx <= last; ++indx)
      {
        cur_val = This[indx];
        if ((*fun_ptr)(prev_val, cur_val) > 0)
        {
          /* out of order: array[indx-1] > array[indx] */
          uint32 indx2;
          This[indx] = prev_val; /* move up the larger item first */

          /* find the insertion point for the smaller item */
          for (indx2 = indx - 1; indx2 > first; )
          {
            int temp_val = This[indx2 - 1];
            if ((*fun_ptr)(temp_val, cur_val) > 0)
            {
              This[indx2--] = temp_val;
              /* still out of order, move up 1 slot to make room */
            }
            else
              break;
          }
          This[indx2] = cur_val; /* insert the smaller item right here */
        }
        else
        {
          /* in order, advance to next element */
          prev_val = cur_val;
        }
      }
    }
    else
    {
      int pivot;

      /* try quick sort */
      {
        int temp;
        uint32 med = (first + last) >> 1;
        /* Choose pivot from first, last, and median position. */
        /* Sort the three elements. */
        temp = This[first];
        if ((*fun_ptr)(temp, This[last]) > 0)
        {
          This[first] = This[last]; This[last] = temp;
        }
        temp = This[med];
        if ((*fun_ptr)(This[first], temp) > 0)
        {
          This[med] = This[first]; This[first] = temp;
        }
        temp = This[last];
        if ((*fun_ptr)(This[med], temp) > 0)
        {
          This[last] = This[med]; This[med] = temp;
        }
        pivot = This[med];
      }
      {
        uint32 up;
        {
  uint32 down;
          /* First and last element will be loop stopper. */
  /* Split array into two partitions. */
  down = first;
  up = last;
  for (;;)
  {
    do
    {
      ++down;
    } while ((*fun_ptr)(pivot, This[down]) > 0);

    do
    {
      --up;
    } while ((*fun_ptr)(This[up], pivot) > 0);

    if (up > down)
    {
      int temp;
      /* interchange L[down] and L[up] */
      temp = This[down]; This[down]= This[up]; This[up] = temp;
    }
    else
      break;
  }
}
{
  uint32 len1; /* length of first segment */
  uint32 len2; /* length of second segment */
  len1 = up - first + 1;
  len2 = last - up;
  /* stack the partition that is larger */
  if (len1 >= len2)
  {
    first_stack[stack_pointer] = first;
    last_stack[stack_pointer++] = up;

    first = up + 1;
    /*  tail recursion elimination of
     *  Qsort(This,fun_ptr,up + 1,last)
     */
  }
  else
  {
    first_stack[stack_pointer] = up + 1;
    last_stack[stack_pointer++] = last;

    last = up;
    /* tail recursion elimination of
     * Qsort(This,fun_ptr,first,up)
     */
  }
}
        continue;
      }
      /* end of quick sort */
    }
    if (stack_pointer > 0)
    {
      /* Sort segment from stack. */
      first = first_stack[--stack_pointer];
      last = last_stack[stack_pointer];
    }
    else
      break;
  } /* end for */
}


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  Qsort(This, fun_ptr, 0, the_len - 1);
}

#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

uint32 fill_array()
{
  int indx;
  uint32 checksum = 0;
  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    checksum += my_array[indx] = rand();
  }
  return checksum;
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;
  uint32 checksum1;
  uint32 checksum2 = 0;
  checksum1 = fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    checksum2 += my_array[indx];
  }

  if (checksum1 != checksum2)
  {
    printf("bad checksum %d %d\n", checksum1, checksum2);
    return(1);
  }

  return(0);
}

 

Start from two sorted runs of length 1, merge into a single run of twice the length. Repeat until a single sorted run is left. Mergesort needs N/2 extra buffer. Performance is second place on average, with quite good speed on nearly sorted array. Mergesort is stable in that two elements that are equally ranked in the array will not have their relative positions flipped.

 

#include
#include


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);



#define INSERTION_SORT_BOUND 8 /* boundary point to use insertion sort */

void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  uint32 span;
  uint32 lb;
  uint32 ub;
  uint32 indx;
  uint32 indx2;

  if (the_len <= 1)
    return;

  span = INSERTION_SORT_BOUND;

  /* insertion sort the first pass */
  {
    int prev_val;
    int cur_val;
    int temp_val;

    for (lb = 0; lb < the_len; lb += span)
    {
      if ((ub = lb + span) > the_len) ub = the_len;

      prev_val = This[lb];

      for (indx = lb + 1; indx < ub; ++indx)
      {
        cur_val = This[indx];

        if ((*fun_ptr)(prev_val, cur_val) > 0)
        {
          /* out of order: array[indx-1] > array[indx] */
          This[indx] = prev_val; /* move up the larger item first */

          /* find the insertion point for the smaller item */
          for (indx2 = indx - 1; indx2 > lb;)
          {
            temp_val = This[indx2 - 1];
            if ((*fun_ptr)(temp_val, cur_val) > 0)
            {
              This[indx2--] = temp_val;
              /* still out of order, move up 1 slot to make room */
            }
            else
              break;
          }
          This[indx2] = cur_val; /* insert the smaller item right here */
        }
        else
        {
          /* in order, advance to next element */
          prev_val = cur_val;
        }
      }
    }
  }

  /* second pass merge sort */
  {
    uint32 median;
    int* aux;

    aux = (int*) malloc(sizeof(int) * the_len / 2);

    while (span < the_len)
    {
      /* median is the start of second file */
      for (median = span; median < the_len;)
      {
        indx2 = median - 1;
        if ((*fun_ptr)(This[indx2], This[median]) > 0)
        {
          /* the two files are not yet sorted */
          if ((ub = median + span) > the_len)
          {
            ub = the_len;
          }

          /* skip over the already sorted largest elements */
          while ((*fun_ptr)(This[--ub], This[indx2]) >= 0)
          {
          }

          /* copy second file into buffer */
          for (indx = 0; indx2 < ub; ++indx)
          {
            *(aux + indx) = This[++indx2];
          }
          --indx;
          indx2 = median - 1;
          lb = median - span;
          /* merge two files into one */
          for (;;)
          {
            if ((*fun_ptr)(*(aux + indx), This[indx2]) >= 0)
            {
              This[ub--] = *(aux + indx);
              if (indx > 0) --indx;
              else
              {
                /* second file exhausted */
                for (;;)
                {
                  This[ub--] = This[indx2];
                  if (indx2 > lb) --indx2;
                  else goto mydone; /* done */
                }
              }
            }
            else
            {
              This[ub--] = This[indx2];
              if (indx2 > lb) --indx2;
              else
              {
                /* first file exhausted */
                for (;;)
                {
                  This[ub--] = *(aux + indx);
                  if (indx > 0) --indx;
                  else goto mydone; /* done */
                }
              }
            }
          }
        }
        mydone:
        median += span + span;
      }
      span += span;
    }

    free(aux);
  }
}

#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

uint32 fill_array()
{
  int indx;
  uint32 sum = 0;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    sum += my_array[indx] = rand();
  }
  return sum;
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;
  uint32 checksum, checksum2;

  checksum = fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  checksum2 = my_array[0];

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    checksum2 += my_array[indx];
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }

  if (checksum != checksum2)
  {
    printf("bad checksum %d %d\n", checksum, checksum2);
    return(1);
  }
  return(0);
}

Form a tree with parent of the tree being larger than its children. Remove the parent from the tree successively. On average, Heapsort is third place in speed. Heapsort does not need extra buffer, and performance is not sensitive to initial distributions.

#include
#include


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* heap sort */

  uint32 half;
  uint32 parent;

  if (the_len <= 1)
    return;

  half = the_len >> 1;
  for (parent = half; parent >= 1; --parent)
  {
    int temp;
    int level = 0;
    uint32 child;

    child = parent;
    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < the_len) &&
          ((*fun_ptr)(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    temp = This[parent - 1];
    for (;;)
    {
      if (parent == child)
        break;
      if ((*fun_ptr)(temp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parent to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = temp;
  }

  --the_len;
  do
  {
    int temp;
    int level = 0;
    uint32 child;

    /* move max element to back of array */
    temp = This[the_len];
    This[the_len] = This[0];
    This[0] = temp;

    child = parent = 1;
    half = the_len >> 1;

    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < the_len) &&
          ((*fun_ptr)(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    for (;;)
    {
      if (parent == child)
        break;
      if ((*fun_ptr)(temp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parent to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = temp;
  } while (--the_len >= 1);
}


#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    my_array[indx] = rand();
  }
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;

  fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }

  return(0);
}

 

Sort every Nth element in an array using insertion sort. Repeat using smaller N values, until N = 1. On average, Shellsort is fourth place in speed. Shellsort may sort some distributions slowly.

#include
#include


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);


/* Calculated from the combinations of  9 * (4^n - 2^n) + 1,
* and  4^n - 3 * 2^n + 1
*/
uint32 hop_array[] =
{
1,
5,
19,
41,
109,
209,
505,
929,
2161,
3905,
8929,
16001,
36289,
64769,
146305,
260609,
587521,
1045505,
2354689,
4188161,
9427969,
16764929,
37730305,
67084289,
150958081,
268386305,
603906049,
1073643521,
2415771649,
0xffffffff };


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* shell sort */

  int level;

  for (level = 0; the_len > hop_array[level]; ++level);

  do
  {
    uint32 dist;
    uint32 indx;
   
    dist = hop_array[--level];
    for (indx = dist; indx < the_len; ++indx)
    {
      int cur_val;
      uint32 indx2;

      cur_val = This[indx];
      indx2 = indx;
      do
      {
        int early_val;
        early_val = This[indx2 - dist];
        if ((*fun_ptr)(early_val, cur_val) <= 0)
          break;
        This[indx2] = early_val;
        indx2 -= dist;
      } while (indx2 >= dist);
      This[indx2] = cur_val;
    }
  } while (level >= 1);
}


#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

uint32 fill_array()
{
  int indx;
  uint32 checksum = 0;
  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    checksum += my_array[indx] = rand();
  }
  return checksum;
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;
  uint32 sum1;
  uint32 sum2;

  sum1 = fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }
  for (indx = 0; indx < ARRAY_SIZE; ++indx)
  {
    sum2 += my_array[indx];
  }
  if (sum1 != sum2)
  {
    printf("bad checksum\n");
    return(1);
  }
  return(0);
}

Sorting algorithms can be mixed and matched to yield the desired properties. We want fast average performance, good worst case performance, and no large extra storage requirement. We can achieve the goal by starting with the Quicksort (fastest on average). We modify Quicksort by sorting small partitions by using Insertion Sort (best with small partition). If we detect two partitions are badly balanced, we sort the larger partition by Heapsort (good worst case performance). Of course we cannot undo the bad partitions, but we can stop the possible degenerate case from continuing to generate bad partitions.

 

#include
#include


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);


void HelperHeapSort(int This[], CMPFUN fun_ptr, uint32 first, uint32 the_len)
{
  /* heap sort */

  uint32 half;
  uint32 parent;

  if (the_len <= 1)
    return;

  half = the_len >> 1;
  for (parent = half; parent >= 1; --parent)
  {
    int temp;
    int level = 0;
    uint32 child;

    child = parent;
    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < the_len) &&
          ((*fun_ptr)(This[first + child], This[first + child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    temp = This[first + parent - 1];
    for (;;)
    {
      if (parent == child)
        break;
      if ((*fun_ptr)(temp, This[first + child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parent to rotation point */
    for (;level > 0; --level)
    {
      This[first + (child >> level) - 1] =
        This[first + (child >> (level - 1)) - 1];
    }
    This[first + child - 1] = temp;
  }

  --the_len;
  do
  {
    int temp;
    int level = 0;
    uint32 child;

    /* move max element to back of array */
    temp = This[first + the_len];
    This[first + the_len] = This[first];
    This[first] = temp;

    child = parent = 1;
    half = the_len >> 1;

    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < the_len) &&
          ((*fun_ptr)(This[first + child], This[first + child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    for (;;)
    {
      if (parent == child)
        break;
      if ((*fun_ptr)(temp, This[first + child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parent to rotation point */
    for (;level > 0; --level)
    {
      This[first + (child >> level) - 1] =
        This[first + (child >> (level - 1)) - 1];
    }
    This[first + child - 1] = temp;
  } while (--the_len >= 1);
}


#define INSERTION_SORT_BOUND 16 /* boundary point to use insertion sort */

/* explain function
* Description:
*   fixarray::Qsort() is an internal subroutine that implements quick sort.
*
* Return Value: none
*/
void Qsort(int This[], CMPFUN fun_ptr, uint32 first, uint32 last)
{
  uint32 stack_pointer = 0;
  int first_stack[32];
  int last_stack[32];

  for (;;)
  {
    if (last - first <= INSERTION_SORT_BOUND)
    {
      /* for small sort, use insertion sort */
      uint32 indx;
      int prev_val = This[first];
      int cur_val;

      for (indx = first + 1; indx <= last; ++indx)
      {
        cur_val = This[indx];
        if ((*fun_ptr)(prev_val, cur_val) > 0)
        {
          uint32 indx2;
          /* out of order */
          This[indx] = prev_val;

          for (indx2 = indx - 1; indx2 > first; --indx2)
          {
            int temp_val = This[indx2 - 1];
            if ((*fun_ptr)(temp_val, cur_val) > 0)
            {
              This[indx2] = temp_val;
            }
            else
              break;
          }
          This[indx2] = cur_val;
        }
        else
        {
          /* in order, advance to next element */
          prev_val = cur_val;
        }
      }
    }
    else
    {
      int pivot;

      /* try quick sort */
      {
int temp;
uint32 med = (first + last) >> 1;
        /* Choose pivot from first, last, and median position. */
        /* Sort the three elements. */
        temp = This[first];
        if ((*fun_ptr)(temp, This[last]) > 0)
        {
          This[first] = This[last]; This[last] = temp;
        }
        temp = This[med];
        if ((*fun_ptr)(This[first], temp) > 0)
        {
          This[med] = This[first]; This[first] = temp;
        }
        temp = This[last];
        if ((*fun_ptr)(This[med], temp) > 0)
        {
          This[last] = This[med]; This[med] = temp;
        }
        pivot = This[med];
      }
      {
        uint32 up;
        {
          uint32 down;
          /* First and last element will be loop stopper. */
          /* Split array into two partitions. */
          down = first;
          up = last;
          for (;;)
  {
    do
    {
      ++down;
    } while ((*fun_ptr)(pivot, This[down]) > 0);

    do
    {
              --up;
            } while ((*fun_ptr)(This[up], pivot) > 0);

    if (up > down)
    {
      int temp;
              /* interchange L[down] and L[up] */
              temp = This[down]; This[down]= This[up]; This[up] = temp;
    }
    else
      break;
  }
}
        {
          uint32 len1; /* length of first segment */
          uint32 len2; /* length of second segment */
          len1 = up - first + 1;
          len2 = last - up;
          if (len1 >= len2)
          {
            if ((len1 >> 5) > len2)
            {
              /* badly balanced partitions, heap sort first segment */
              HelperHeapSort(This, fun_ptr, first, len1);
            }
            else
            {
              first_stack[stack_pointer] = first; /* stack first segment */
              last_stack[stack_pointer++] = up;
            }
            first = up + 1;
            /*  tail recursion elimination of
             *  Qsort(This,fun_ptr,up + 1,last)
             */
          }
          else
          {
            if ((len2 >> 5) > len1)
            {
              /* badly balanced partitions, heap sort second segment */
              HelperHeapSort(This, fun_ptr, up + 1, len2);
            }
            else
            {
              first_stack[stack_pointer] = up + 1; /* stack second segment */
              last_stack[stack_pointer++] = last;
            }
            last = up;
            /* tail recursion elimination of
             * Qsort(This,fun_ptr,first,up)
             */
          }
        }
        continue;
      }
      /* end of quick sort */
    }
    if (stack_pointer > 0)
    {
      /* Sort segment from stack. */
      first = first_stack[--stack_pointer];
      last = last_stack[stack_pointer];
    }
    else
      break;
  } /* end for */
}


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  Qsort(This, fun_ptr, 0, the_len - 1);
}

#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    my_array[indx] = rand();
  }
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;

  fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }

  return(0);
}