Listing 1

#include "stdafx.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"

int main(int argc, char* argv[])
{
  // Variable declarations
  const int ListLength = 100;
  int a[ListLength], b[ListLength], c[ListLength];
  int x, y, HighestSeen, LowestSeen, EntryValue, EntryStep;
  int HighestBelow, HighestBelowPos, CurrentPosition, Buffer1;
  int Buffer2, HighestEntry, LowestEntry;
  bool IsLower, IsHigher, IsNotGreater;

  // The list would be read or otherwise accessed at this point

  // Sort list
  HighestEntry = 0;
  LowestEntry = ListLength + 1;
  HighestSeen = 0;
  LowestSeen = 0;

  for (x=0; x < ListLength; x++)
  {
    EntryValue = a[x];
    IsLower = false;
    IsHigher = false;
    
    // Is it the lowest value so far?
    if (EntryValue < LowestEntry)
    {
      IsLower = true;
      b[x] = LowestSeen;
      LowestEntry = EntryValue;
      LowestSeen = x;
    }
    // Is it the highest value so far?
    if (EntryValue >= HighestEntry)
    {
      IsHigher = true;
      b[HighestSeen] = x;
      b[x] = 0;
      HighestEntry = EntryValue;
      HighestSeen = x;
    }
    // If not lowest or highest, find the next-lowest value
    if (!IsLower && !IsHigher)
    {
      // Jump through list to find any lower value
      EntryStep = 1 + (int)sqrt(x);
      HighestBelow = 0;
      for (y=0; y < x; y += EntryStep)
      {
        if (a[y] > HighestBelow && a[y] < EntryValue)
        {
          HighestBelow = a[y];
          HighestBelowPos = y;
        }
      }
      // If lower value not found, use lowest value
      if (HighestBelow == 0)
      {
        HighestBelow = LowestEntry;
        HighestBelowPos = LowestSeen;
      }
      // Loop through list to find highest lower value
      IsNotGreater = true;
      CurrentPosition = HighestBelowPos;
      while(IsNotGreater)
      {
        Buffer1 = CurrentPosition;
        CurrentPosition = b[CurrentPosition];
        if (a[CurrentPosition] > EntryValue)
        {
          IsNotGreater = false;
          Buffer2 = CurrentPosition;
        }
      }
      // Change list
      b[Buffer1] = x;
      b[x] = Buffer2;
  }
  }
  // Carry out sorting
  CurrentPosition = LowestSeen;
  for (x=0; x < ListLength; x++)
  {
    c[x] = a[CurrentPosition];
    CurrentPosition = b[CurrentPosition];
  }
  return 0;
}