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

int *resize_array(int *a, size_t new_size)
{
    int *save;
    save = realloc(a, new_size);

    if (save == NULL) {
        fprintf(stderr, "Memory exhuasted\n");
        exit(EXIT_FAILURE);
    }

    return save;
}

int *quicksort(int *array, size_t size)
{
    int lesser[size], less_counter = 0;
    int greater[size], great_counter = 0;

    if (size < 2)
        return array;

    // Take last element and make it the pivot, then subtract one
    // from size afterwards so that it will no longer be accesssed
    int pivot = array[size - 1];
    size--;

    for(unsigned int i = 0; i < size; i++){
        if (array[i] <= pivot){
            lesser[less_counter++] = array[i];
        }
        else {
            greater[great_counter++] = array[i];
        }
    }

    int *lesser_sorted = quicksort(lesser, (size_t)less_counter);
    int *greater_sorted = quicksort(greater, (size_t)great_counter);

    int main_counter;
    for(main_counter = 0; main_counter < less_counter; main_counter++){
        array[main_counter] = lesser_sorted[main_counter];
    }

    array[main_counter++] = pivot;

    for (int i = 0; i < great_counter; i++){
        array[main_counter] = greater_sorted[i];
        main_counter++;
    }

    return array;
}

int main()
{
    int size = 1;
    int *numbers = malloc(size * sizeof *numbers);
    int *temp = malloc(size * sizeof *temp);
    int error;

    /// Loop through stdin stream grabbing `size` numbers each iteration
    while ((error = fread(temp, sizeof *numbers, 1, stdin))){
        // Should not happen if EOF has been reached or we have loaded all data
        // May happen if we reached EOF at exactly size [didn't find clear documention], in which case next iteration should catch it
        if (error != 0){
            numbers[size - 1] = temp[0];
            size++;
            numbers = resize_array(numbers, size * sizeof *numbers);
        }
    }
    size--;

    int *sorted_numbers = quicksort(numbers, size);
    for (int i = 0; i < size; i++){
        printf("%i\n", sorted_numbers[i]);
    }

    free(temp);
    free(sorted_numbers);
    return 0;
}