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

int print_arr(const int* arr, const int size)
{
    printf("array: ");
    for (int i = 0; i < size; i++)
    {
        printf ("%d ", arr[i]);
    }
    printf("\n");
}

int q_sort(int* arr, const int first, const int last)
{
    int size = last - first + 1;

    printf("start sort. ");
    print_arr(arr, size);

    if (size == 2)
    {
        printf("hi!");
        if (arr[0] > arr[1])
        {
            int x = arr[1];
            arr[1] = arr[0];
            arr[0] = x;
        }
        return 0;
    }

    if (size <= 1)
    {
        return 0;
    }

    int middle_index = (int)(size / 2);
    printf("middle_index = %d\n", middle_index);

    int begin_index = first;
    int end_index = last;

    int current_left_index = 0;
    int left_size = 0;
    int* left_arr  = (int*)malloc(size*sizeof(int));

    int current_right_index = 0;
    int right_size = 0;
    int* right_arr = (int*)malloc(size*sizeof(int));

    int current_middle_index = 0;
    int middle_size = 0;
    int* middle_arr  = (int*)malloc(size*sizeof(int));

    int middle_element = arr[middle_index];

    for (int i = begin_index; i <= end_index; i++)
    {
        printf("if. current element: %d, middle: %d\n", arr[i], middle_element);
        if (arr[i] >= middle_element)
        {
            right_arr[current_right_index] = arr[i];
            current_right_index++;
            right_size++;
        }

        if (arr[i] < middle_element)
        {
            left_arr[current_left_index] = arr[i];
            current_left_index++;
            left_size++;
        }

        if (arr[i] == middle_element)
        {
            middle_arr[current_middle_index] = arr[i];
            current_middle_index++;
            middle_size++;
        }
    }

    printf("left_size: %d\n", left_size);
    printf("result left array: ");
    print_arr(left_arr, left_size);
    q_sort(left_arr,  0, left_size - 1);

    for (int i = 0; i < left_size; i++)
    {
        arr[i] = left_arr[i];
    }

    printf("middle_size: %d\n", middle_size);
    printf("result middle array:");
    print_arr(middle_arr, middle_size);

    for (int i = 0; i < middle_size; i++)
    {
        arr[i + left_size + 1] = middle_arr[i];
    }

    printf("right_size: %d\n", right_size);
    printf("result right array:");
    print_arr(right_arr, right_size);
    q_sort(right_arr, 0, right_size - 1);

    for (int i = 0; i < right_size; i++)
    {
        arr[i + middle_size + left_size + 1] = right_arr[i];
    }

    free(right_arr);
    free(left_arr);
}

int main()
{
    int size = 0;
    int array[1000];
    printf ("Enter the length of the array\n");
    scanf ("%d", &size);
    printf ("Enter the elements of the array\n");

    for (int i = 0; i < size; i++)
    {
        scanf ("%d", &array[i]);
    }

    int last = size - 1;
    int first = 0;

    q_sort(array, first, last);

    printf ("\nSorted array:\n");
    print_arr(array, size);

    return 0;
}