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

// Resizes array a using realloc
unsigned int *resize_array(unsigned int *a, size_t new_size)
{
    unsigned int *save;
    save = realloc(a, new_size);

    if (save == NULL) {
        fprintf(stderr, "Realloc failed, cannot resize array.\n");
        exit(EXIT_FAILURE);
    }

    return save;
}

// Swaps the values of a and b
void swap(unsigned int *a, unsigned int *b){
    unsigned int old_a = *a;
    *a = *b;
    *b = old_a;
}

// Creates a partition for use by quicksort
int partition(unsigned int *array, int left, int right, int pivot){
    unsigned int pivot_value = array[pivot];
    swap(&array[pivot], &array[right]);
    int storeIndex = left;
    for(int i = left; i < right; i++){
        if (array[i] < pivot_value){
            swap(&array[i], &array[storeIndex]);
            storeIndex++;
        }
    }

    swap(&array[storeIndex], &array[right]);

    return storeIndex;
}

// Using partition to sort `array`
void quicksort(unsigned int *array, int left, int right){
    if (left < right){
        int pivot = right;

        pivot = partition(array, left, right, pivot);
        quicksort(array, left, pivot - 1);
        quicksort(array, pivot + 1, right);
    }
}

int main()
{
    const int temp_size = 50; // How many numbers to load at once?
    int size = 1;

    // Holds all numbers we need to sort
    unsigned int *numbers = malloc(size * sizeof *numbers);

    // Holds the numbers recently pulled from the stream
    unsigned int *temp = malloc(temp_size * sizeof *temp);

    int ret_val; // Holds the return value of fread so we know how many numbers were read

    /// Loop through stdin stream grabbing `temp_size` numbers each iteration
    while ((ret_val = fread(temp, sizeof *temp, temp_size, stdin))){
        // Should not happen if EOF has been reached/we have loaded all data
        if (ret_val != 0){

            // This looks complicated, just the math required to figure the new size of `numbers`
            int new_size = size - 1 + ret_val;

            // Actually resize array
            numbers = resize_array(numbers, new_size * sizeof *numbers);

            // Go from size to new_size, putting the numbers from `temp` into `numbers`
            int temp_count = 0;
            for(int i = size - 1; i < new_size; i++){
                numbers[i] = temp[temp_count++];
            }

            // Update `size`, now that we are done with it's previous value
            size = new_size;
        }
    }


    quicksort(numbers, 0, size - 1);

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

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