// Created by Alessandro Lo-Presti (Agilo) on October 7, 2008.
#include<stdio.h>


// Turn debugging on to see the process.
#define DEBUG 0


// I was bored, so I made this quicksort function.
int *quicksort(int *list, int len) {
 if (len <= 1) return list;

 int i, j, s, g, piv, smallerlist[len<<1], greaterlist[len<<1];

 // Assign entries to a list (either greater or smaller than the pivot).
 // Also note that the first entry is the pivot (which is skipped).
 for (i=1, s=0, g=0; i<len; i++) {
  if (list[i] < list[0]) {
   smallerlist[s++] = list[i];
  } else {
   greaterlist[g++] = list[i];
  }
 }

 // Debugging crap.
 if (DEBUG) {
  printf("---\n");
  for (i=0; i<g; i++) printf("g Number: %d\n", greaterlist[i]);
  printf("p Number: %d\n", list[0]);
  for (i=0; i<s; i++) printf("s Number: %d\n", smallerlist[i]);
  printf("---\n");
 }

 // Sort the greater/smaller lists.
 int *sorted_great_list = quicksort(greaterlist, g),
     *sorted_small_list = quicksort(smallerlist, s);

 // Save the pivot.
 piv = list[0];

 // Build/Rewrite the list to return.
 for (i=0, j=0; i<g; i++) list[j++] = sorted_great_list[i];
 list[j++] = piv;
 for (i=0; i<s; i++) list[j++] = sorted_small_list[i];

 // Debugging crap.
 if (DEBUG) printf("Returning...\n");

 // Return the sorted list.
 return list;
}


int main() {
 int i, list[16] = {5,8,11,2,13,12,4,7,15,1,14,6,9,0,10,3}, listlen = (sizeof(list)/sizeof(list[0]));

 // Debugging crap.
 if (DEBUG) printf("Length: %d\n", listlen);

 // Sort the list.
 int *sortedlist = quicksort(list, listlen);

 // Debugging crap.
 if (DEBUG) printf("Sorted\n");

 // Show the sorted list.
 for (i=0; i<listlen; i++) printf("Number: %d\n", sortedlist[i]);

 // Return safely to the warmth of the OS.
 return 0;
}