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

struct queue {
  struct queue *next;
  int high, low;
};

void read_input(int **list, int *size);
void flash_sort(int *list, int size);
void hulk_sort(int *list, int low, int high);
void swap_values(int *first, int *second);
int select_pivot(int *list, int low, int high);
void write_output(int *list, int size);

int main() {
  int size;
  int *list;

  srand(time(NULL));

  read_input(&list, &size);
  flash_sort(list, size);
  write_output(list, size);

  return 0;
}

void read_input(int **list, int *size) {
  FILE *input = fopen("algsort.in", "r");

  fscanf(input, "%d\n", size);

  *list = malloc(sizeof(int) * (*size));

  for (int index = 0; index < *size; index +=1) {
    fscanf(input, "%d", *list + index);
  }

  fclose(input);
}

void flash_sort(int *list, int size) {
  int pivot, pivot_position, sort_threshold;
  int left, left_low, right, right_high;

  struct queue *partition, *last_partition, *new_partition;

  partition = malloc(sizeof(struct queue));

  sort_threshold = 5;

  left_low   = 0;
  right_high = size -1;

  partition->next = NULL;
  partition->high = right_high;
  partition->low  = left_low;

  last_partition = partition;

  while(partition != NULL) {
    left_low   = partition->low;
    right_high = partition->high;

    if (right_high - left_low <= sort_threshold) {
      hulk_sort(list, left_low, right_high);

      partition = partition->next;
      continue;
    }

    pivot_position = select_pivot(list, left_low, right_high);

    left  = left_low;
    right = right_high;

    pivot = list[pivot_position];

    while (left <= right) {
      while(list[left]  < pivot && left  < right_high) left  += 1;
      while(list[right] > pivot && right > left_low)   right -= 1;

      if (left <= right) {
        if (list[left] > list[right]) swap_values(&list[left], &list[right]);
        left  += 1;
        right -= 1;
      };
    }

    if (left_low < right) {
      new_partition = malloc(sizeof(struct queue));

      new_partition->next = NULL;
      new_partition->high = right;
      new_partition->low  = left_low;

      last_partition->next = new_partition;
      last_partition = new_partition;
    }

    if (left < right_high) {
      new_partition = malloc(sizeof(struct queue));

      new_partition->next = NULL;
      new_partition->high = right_high;
      new_partition->low  = left;

      last_partition->next = new_partition;
      last_partition = new_partition;
    }

    partition = partition->next;
  }
}

void hulk_sort(int *list, int low, int high) {
  for (int first = low; first < high; first += 1) {
    for (int second = first + 1; second <= high; second += 1) {
      if (list[first] > list[second]) {
        swap_values(&list[first], &list[second]);
      }
    }
  }
}

void swap_values(int *first, int *second) {
  int carry;

  carry   = *first;
  *first  = *second;
  *second = carry;
}

int select_pivot(int *list, int low, int high) {
  return rand() % (high - low) + low;
}

void write_output(int *list, int size) {
  FILE *output = fopen("algsort.out", "w");

  int last = size - 1;

  for (int index = 0; index < size; index +=1) {
    if (index < last) {
      fprintf(output, "%d ", list[index]);
    } else {
      fprintf(output, "%d", list[index]);
    }
  }
  fprintf(output, "\n");

  fclose(output);
}