#include <stdio.h>
#include <stdlib.h>

void sort (int *, unsigned);

int main (void) {
  int * array = NULL;
  unsigned length = 0;
  printf("Input a number, anything invalid to quit: ");
  int entry;
  int status;
  for (status = scanf("%d", &entry); status; status = scanf("%d", &entry)) {
    array = realloc(array, sizeof(int) * (length ++));
    array[length - 1] = entry;
    printf("Input a number, anything invalid to quit: ");
  }
  sort(array, length);
  printf("Result: ");
  for (entry = 0; entry < length; entry ++) printf("%d ", array[entry]);
  putchar('\n');
  free(array);
  return 0;
}

void sort (int * array, unsigned arrayLength) {
  int * first = array;
  int * last = array + (arrayLength - 1);
  int * current = first;
  int temp;
  while (first != last) {
    if (*first < *last) {
      temp = *first;
      *first = *last;
      *last = temp;
      current = (current == first) ? last : first;
    }
    if (current == last)
      first ++;
    else
      last --;
  }
  if ((current - array) > 1)
    if ((current - array) == 2) {
      if (*array < array[1]) {
        temp = *array;
        *array = array[1];
        array[1] = *array;
      }
    } else
      sort(array, current - array);
  if ((current - array) < (arrayLength - 2))
    if ((current - array) == (arrayLength - 3)) {
      if (current[1] < current[2]) {
        temp = current[1];
        current[1] = current[2];
        current[2] = temp;
      }
    } else
      sort(current + 1, arrayLength - 1 - (current - array));
}