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

void read_input(int **list, int *size);
void flash_sort(int *list, int size);
void hulk_sort(int *list, int low, int high);
void exchange(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 = (int*) 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, carry;
  int left, left_low, left_high, right, right_low, right_high;

  int equal_left, equal_right;

  int *partition_low, *partition_high;
  int partition_size, partition_start, partition_end;

  partition_size  = 200000; //(int)  ceil(log2((float) size) * 3);
  partition_low   = (int*) malloc(sizeof(int) * (partition_size));
  partition_high  = (int*) malloc(sizeof(int) * (partition_size));

  sort_threshold = 10;

  left_low   = 0;
  right_high = size -1;

  partition_start = -1;
  partition_end   = 0;

  partition_low[partition_end]  = left_low;
  partition_high[partition_end] = right_high;

  // printf("List: ");
  for (int index = 0; index < size; index +=1) {
    // printf("%d ", list[index]);
  }
  // printf("\n");

  while(partition_start < partition_end) {
    partition_start += 1;

    // printf("Start: %d End: %d\n", partition_start, partition_end);

    left_low   = partition_low[partition_start];
    right_high = partition_high[partition_start];

    equal_left  = left_low;
    equal_right = right_high;

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

      // printf("Insertion: %d %d\n", left_low, right_high);

      // printf("List: ");
      for (int index = 0; index < size; index +=1) {
        // printf("%d ", list[index]);
      }
      // printf("\n");

      continue;
    }

    pivot_position = select_pivot(list, left_low, right_high);

    // printf("Position: %d Pivot: %d\n", pivot_position, list[pivot_position]);

    left  = left_low;
    right = right_high;

    pivot = list[pivot_position];

    // printf("Range: %d - %d\n", left, right);

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

      // printf("Left: %d Right: %d Position: %d\n", left, right, pivot_position);

      // printf("List Before: ");
      for (int index = 0; index < size; index +=1) {
        // printf("%d ", list[index]);
      }
      // printf("\n");

      if (left >= right) break;

      exchange(&list[left], &list[right]);

      if (list[left] == pivot) {
        exchange(&list[left], &list[equal_left]);
        equal_left += 1;
      }

      if (list[right] == pivot) {
        exchange(&list[right], &list[equal_right]);
        equal_right -= 1;
      }

      // printf("Pivot Position: %d\n", pivot_position);
      // printf("EQL: %d EQR: %d\n", equal_left, equal_right);

      // printf("List After:  ");
      for (int index = 0; index < size; index +=1) {
        // printf("%d ", list[index]);
      }
      // printf("\n");
    }

    for (int index = left_low; index < equal_left; index += 1) {
      exchange(&list[index], &list[equal_left]);
      equal_left -= 1;
    }

    left_high = equal_left;

    if (left_high > left_low) {
      partition_end                 += 1;
      partition_high[partition_end] = left_high;
      partition_low[partition_end]  = left_low;

      // printf("Added: %d %d\n", partition_high[partition_end], partition_low[partition_end]);
    }

    for (int index = right_high; index > equal_right; index -= 1) {
      exchange(&list[index], &list[equal_right]);
      equal_right += 1;
    }

    right_low = equal_right;

    if (right_low < right_high) {
      partition_end                 += 1;
      partition_high[partition_end] = right_high;
      partition_low[partition_end]  = right_low;

      // printf("Added: %d %d\n", partition_high[partition_end], partition_low[partition_end]);
    }
  }
}

void hulk_sort(int *list, int low, int high) {
  int carry;

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

void exchange(int *left, int *right) {
  int carry  = *left;
  *left      = *right;
  *right     = 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);
}