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

void stackSort(int a[], int n)
{
    int *manji = malloc(n * sizeof(int));
    int *veci = malloc(n * sizeof(int));

    int i_manji = -1, i_veci = -1;

    if (manji == NULL)
    {
        fprintf(stderr, "Greska pri alokaciji memorije\n");
        exit(EXIT_FAILURE);
    } 
    if (veci == NULL)
    {
        fprintf(stderr, "Greska pri alokaciji memorije\n");
        free(manji);
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < n; i++)
    {
        // Pomera elemente iz manji u veci dok su veci od trenutnog elementa
        while (i_manji != -1 && manji[i_manji] > a[i])
            veci[++i_veci] = manji[i_manji--];
        // Pomera elemente iz veci u manji dok su manji od trenutnog elementa
        while (i_veci != -1 && veci[i_veci] < a[i])
            manji[++i_manji] = veci[i_veci--];

        manji[++i_manji] = a[i];
    }

    for (int i = 0; i <= i_manji; i++)
        a[i] = manji[i];

    for (int i = i_veci, j = i_manji + 1; i >= 0; i--)
        a[j++] = veci[i];

    free(manji);
    free(veci);
}

int main(void)
{
    int niz[] = { 7, 3, 5, 1, 9, 2 };
    int n = sizeof(niz) / sizeof(niz[0]);

    printf("Pre sortiranja:\n");
    for (int i = 0; i < n; ++i)
        printf("%d ", niz[i]);
    printf("\n\n");

    stackSort(niz, n);

    printf("Posle stek sorta:\n");
    for (int i = 0; i < n; ++i)
        printf("%d ", niz[i]);
    printf("\n");

    return 0;
}