#include <stdio.h>
 
#define MAX_VALS 1000
 
int count, c;
int values[MAX_VALS];
int index, value, pos;
int intros, inserts, heaps;
int child, temp, length;
int sp, left, right, pivot;
int stack[1024], part;
double elapsed;
int sppart, sproot, spstart, spend;
FILE*fp;
 
/* ---------------------------------------------------------------------------
 * loadFile
 * Purpose:
 *   Read up to MAX_VALS integers from a text file into the global values array.
 * Parameters:
 *   fspec - input file path to open and read.
 * Returns:
 *   Number of values loaded; returns zero if the file cannot be opened.
 * Variables used:
 *   fp - file handle; c - array index; count - global number of loaded values.
 * --------------------------------------------------------------------------- */
int loadFile(fspec)
char *fspec;
{
     count = 0;
     printf("READING INPUT FILE...");
     fp = fopen(fspec, "rt");
     if (!fp)
     {
          printf("\ERROR %d.\n", errno);
          return 0;
     }
     for (c = 0; c < MAX_VALS; c++)
     {
          if (fscanf(fp, "%d", &values[c]) != 1)
          {
               break ;
          }
          count++;
     }
     fclose(fp);
     printf("DONE.\n");
     
     return count;
}
/* ---------------------------------------------------------------------------
 * saveFile
 * Purpose:
 *   Write each value in the global values array to a text file on its own line.
 * Parameters:
 *   fspec - output file path to create or replace.
 * Returns:
 *   No value; reports an open failure and otherwise closes the output file.
 * Variables used:
 *   fp - output file handle; c - index over values[0..count).
 * --------------------------------------------------------------------------- */
saveFile(fspec)
char *fspec;
{
 
     printf("SAVING OUTPUT FILE...");
     fp = fopen(fspec, "wt");
     if (!fp)
     {
          printf("\nERROR %d.\n", errno);
          return ;
     }
     
     for (c = 0; c < count; c++)
     {
          fprintf(fp, "%d\n", values[c]);
     }
     fclose(fp);
     printf("DONE.\n");
}
 
/* ---------------------------------------------------------------------------
 * siftDown
 * Purpose:
 *   Restore the max-heap property below root within the selected array range.
 * Parameters:
 *   root - subtree root index; start - inclusive heap start; end - exclusive
 *   heap end. The routine operates on the global values array.
 * Returns:
 *   No value; moves values within the range as needed.
 * Variables used:
 *   child - larger child index; temp - value exchanged during a sift.
 * --------------------------------------------------------------------------- */
siftDown(root, start, end)
int root, start, end;
{
     while (start+2*(root-start)+1 < end)
     {
          child = start+2*(root-start)+1;
          if (child+1 < end && values[child] < values[child+1])
          {
               child++;
          }
          if (values[root] >= values[child])
          {
               return ;
          }
          temp = values[root];
          values[root] = values[child];
          values[child] = temp;
          root = child;
     }
}
 
/* ---------------------------------------------------------------------------
 * heapSort
 * Purpose:
 *   Sort the specified range in ascending order using heapsort as introsort's
 *   depth-limit fallback.
 * Parameters:
 *   start - inclusive range start; end - exclusive range end. Uses global values.
 * Returns:
 *   No value; sorts in place and increments the heapsort call counter.
 * Variables used:
 *   root - heap-build position; last - extraction boundary; globals child/temp
 *   support siftDown.
 * --------------------------------------------------------------------------- */
heapSort(start, end)
int start, end;
{
     int root, last;
     heaps++;
     for (root = start+(end-start)/2-1; root >= start; root--)
     {
          siftDown(root, start, end);
     }
     for (last = end-1; last > start; last--)
     {
          temp = values[start];
          values[start] = values[last];
          values[last] = temp;
          siftDown(start, start, last);
     }
}
 
/* ---------------------------------------------------------------------------
 * insertionSort
 * Purpose:
 *   Sort a short range of the global values array using insertion sort.
 * Parameters:
 *   start - inclusive range start; end - exclusive range end.
 * Returns:
 *   No value; sorts in place and increments the insertion-sort call counter.
 * Variables used:
 *   index - next item to insert; value - saved item; pos - insertion scan index.
 * --------------------------------------------------------------------------- */
insertionSort(start, end)
int start, end;
{
     inserts++;
     
     for (index = start; index < end; index++)
     {
          value = values[index];
          pos = index-1;
          while (pos >= start && values[pos] > value)
          {
               values[pos+1] = values[pos];
               pos--;
          }
          values[pos+1] = value;
     }
}
 
/* ---------------------------------------------------------------------------
 * partition
 * Purpose:
 *   Rearrange a range around its middle value to divide introsort's work.
 * Parameters:
 *   start - inclusive range start; end - exclusive range end. Uses global values.
 * Returns:
 *   Index of the first element in the right partition.
 * Variables used:
 *   left, right - inward-moving scan indices; pivot - chosen comparison value.
 * --------------------------------------------------------------------------- */
int partition(start, end)
int start, end;
{
     left = start;
     right = end-1;
     pivot = values[start+(end-start)/2];
     while (left <= right)
     {
          while (values[left] < pivot)
          {
               left++;
          }
          while (values[right] > pivot)
          {
               right--;
          }
          if (left <= right)
          {
               temp = values[left];
               values[left] = values[right];
               values[right] = temp;
               left++;
               right--;
          }
     }
     return left;
}
 
/* ---------------------------------------------------------------------------
 * introSort
 * Purpose:
 *   Sort a range by using insertion sort for small ranges, heapsort when the
 *   partition budget is exhausted, and partitioning otherwise.
 * Parameters:
 *   start - inclusive range start; end - exclusive range end; maxdepth -
 *   remaining partition budget. Operates on global values.
 * Returns:
 *   No value; sorts in place and increments the introsort call counter.
 * Variables used:
 *   length - current range size; part - partition boundary; stack helpers save
 *   the boundary while the left partition is processed.
 * --------------------------------------------------------------------------- */
introSort(start, end, maxdepth)
int start, end, maxdepth;
{
     intros++;
     length = end-start;
     if (length <= 1)
     {
          return ;
     }
     if (length < 16)
     {
          insertionSort(start, end);
     }
     else 
     {
          if (maxdepth <= 0)
          {
               heapSort(start, end);
          }
          else 
          {
               part = partition(start, end);
               push(part); /* Preserve the right partition's start across the left recursion. */
               introSort(start, part, maxdepth-1);
               sppart = pop();
               introSort(sppart, end, maxdepth-1);
          }
     }
}
/* ---------------------------------------------------------------------------
 * log2
 * Purpose:
 *   Estimate the base-two logarithm by repeatedly halving a positive integer.
 * Parameters:
 *   v - positive integer to reduce.
 * Returns:
 *   Number of divisions performed before the value reaches zero.
 * Variables used:
 *   n - accumulated division count; v is reduced in place as a local parameter.
 * --------------------------------------------------------------------------- */
int log2(v)
int v;
{
     int num;
     num = 0;
     while (v > 0)
     {
          v /= 2;
          num++;
     }
     return num;
}
 
/* ---------------------------------------------------------------------------
 * performSort
 * Purpose:
 *   Time introsort over all loaded values using a depth limit of 2*log2(count).
 * Parameters:
 *   None; operates on the global values array and count.
 * Returns:
 *   Elapsed duration in seconds.
 * Variables used:
 *   maxdepth - partition budget; startTime and endTime - timer snapshots.
 * --------------------------------------------------------------------------- */
double performSort()
{
     int maxdepth;
     double startTime, endTime;
     printf("SORTING ELEMENTS...");
     startTime = Tgettime();
     maxdepth = count;
     if (maxdepth > 1)
     {
          maxdepth = log2(count)*2;
     }
     introSort(0, count, maxdepth);
     endTime = Tgettime();
     printf("DONE.\n");
     return endTime-startTime;
}
 
/* ---------------------------------------------------------------------------
 * pop
 * Purpose:
 *   Retrieve the most recently saved partition boundary from the global stack.
 * Parameters:
 *   None; uses the global stack and stack pointer sp.
 * Returns:
 *   The boundary at the prior top of the stack.
 * Variables used:
 *   sp - decremented before the selected stack entry is returned.
 * --------------------------------------------------------------------------- */
int pop()
{
     sp--;
     return stack[sp];
}
/* ---------------------------------------------------------------------------
 * push
 * Purpose:
 *   Save a partition boundary for later use by the introsort traversal.
 * Parameters:
 *   p - partition boundary to store in the global stack.
 * Returns:
 *   No value; advances the global stack pointer sp.
 * Variables used:
 *   sp - index of the next stack slot to fill.
 * --------------------------------------------------------------------------- */
push(p)
int p;
{
     stack[sp] = p;
     sp++;
}
 
/* ---------------------------------------------------------------------------
 * main
 * Purpose:
 *   Load the input, sort the values, save the result, and report elapsed time
 *   and the number of times each sorting routine ran.
 * Parameters:
 *   None; input and output paths are configured in this routine.
 * Returns:
 *   Program exit status after waiting for the keyboard event.
 * Variables used:
 *   temp - number of values loaded; elapsed - duration returned by performSort;
 *   global intros, inserts, and heaps count calls to each sorting method.
 * --------------------------------------------------------------------------- */
int main()
{
     printf("\n=======INTROSORT HiSoft C=======\n");
     temp = loadFile("C:\\INPUT.TXT");
     if (temp > 0)
     {
          elapsed = performSort();
          saveFile("C:\\OUTPUT.TXT");
     }
     printf("==========RUN COMPLETE==========\n");
     printf("INTROSORT TOOK %f SECONDS.\n", elapsed);
     printf("================================\n");
     printf("SORT CALLED | TIMES\n");
     printf("------------+-------------------\n");
     printf("Intro       | %d\n", intros);
     printf("Insertion   | %d\n", inserts);
     printf("Heap        | %d\n", heaps);
     printf("================================\n");
     
     evnt_keybd();
     return 1;
}