//быстрая сортировка с объяснением - DONE
//если предыдущая часть программы не нужна - можно стереть, натравив алгоритм на любой рандомный массив

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

void qs(int* s_arr, int first, int last)
{
    int i = first, j = last, x = s_arr[(first + last) / 2]; //выделяем начало, конец, середину
    do { //теперь нам надо чтобы меньшие середины значения были левее, большие - правее
        while (s_arr[i] < x) i++;   //находим первый эл-т слева > середины
        while (s_arr[j] > x) j--;   //и аналогично первый справа, < середины

        if(i <= j) {                //и если они не на своих местах - меняем местами
            if (s_arr[i] > s_arr[j])
            {
                int sw = s_arr[i];
                s_arr[i] = s_arr[j];
                s_arr[j] = sw;
            }
            i++;
            j--;
        }
    } while (i <= j);//в итоге получили массив, где в левой части значения меньше середины
                    //а справа - больше

    if (i < last)
        qs(s_arr, i, last);//повторяем для левой половины
    if (first < j)
        qs(s_arr, first, j);//повторяем для правой половины
}

int main()
{
    int length = 0;
    printf("Input the length of first array\n");
    scanf("%d", &length);
    const int length1 = length;
    int arr1[length1];
    int i;
    for (i = 0; i < length1; i++)
    {
        printf("Input next element of first array\n");
        scanf("%d", &arr1[i]);
    }

    printf("\nInput the length of second array\n");
    scanf("%d", &length);
    const int length2 = length;
    int arr2[length2];
    for (i = 0; i < length2; i++)
    {
        printf("Input next element of second array\n");
        scanf("%d", &arr2[i]);
    }

    printf("First array: ");
    for (i = 0; i < length1; i++) printf("%d ", arr1[i]);
    printf("\nSecond array: ");
    for (i = 0; i < length2; i++) printf("%d ", arr2[i]);

    const length3 = length1 + length2;
    int arr3[length3];
    int i1 = 0; int i2 = 0; int i3 = 0;
    while (i1 < length1 && i2 < length2)
    {
        if (arr1[i1] < arr2[i2])
        {
            arr3[i3] = arr1[i1];
            i1++;
        }
        else
        {
            arr3[i3] = arr2[i2];
            i2++;
        }
        i3++;
    }

    while (i1 < length1)
    {
        arr3[i3] = arr1[i1];
        i1++;
        i3++;
    }

    while (i2 < length2)
    {
        arr3[i3] = arr2[i2];
        i2++;
        i3++;
    }

    printf("\nMerged array: ");
    for (i = 0; i < length3; i++) printf("%d ", arr3[i]);

    qs(arr3, 0, length3-1);
    printf("\nQuicksorted array (but it was already sorted before): ");
    for (i = 0; i < length3; i++) printf("%d ", arr3[i]);
    return 0;
}