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

typedef struct _CC_VECTOR {
    // Members
    int Capacity;
    int Size;
    int *Elements;
} CC_VECTOR;

int VecCreate(CC_VECTOR **Vector);
int VecDestroy(CC_VECTOR **Vector);

int VecInsertTail(CC_VECTOR *Vector, int Value);
int VecInsertHead(CC_VECTOR *Vector, int Value);
int VecInsertAfterIndex(CC_VECTOR *Vector, int Index, int Value);
int VecRemoveByIndex(CC_VECTOR *Vector, int Index);
int VecGetValueByIndex(CC_VECTOR *Vector, int Index, int *Value);
int VecGetCount(CC_VECTOR *Vector);
int VecClear(CC_VECTOR *Vector);
int VecSort(CC_VECTOR *Vector);

int main()
{
    FILE *rfile = fopen("algsort.in", "r");
    FILE *wfile = fopen("algsort.out", "w");
    CC_VECTOR *vector = NULL;
    VecCreate(&vector);
    srand(time(NULL));
    int n;
    fscanf(rfile, "%d", &n);
    //scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int val;
        fscanf(rfile, "%d", &val);
        //scanf("%d", &val);
        //val = rand();
        VecInsertTail(vector, val);
    }
    VecSort(vector);

    int elem = -1;
    for(int i = 0; i < n; i++)
    {
        VecGetValueByIndex(vector, i, &elem);
        fprintf(wfile, "%d ", elem);
        //printf("%d ", elem);
    }

    fclose(rfile);
    fclose(wfile);
    return 0;
}

// auxiliary function
int VecBackupElementsIncludingIndex(CC_VECTOR *Vector, int Index, int **BackupElementsArray)
{
    // can't backup after last element
    if (Index < 0 || Index > Vector->Size - 1 || NULL != *BackupElementsArray)
    {
         return -1;
    }

    CC_VECTOR *vector = Vector;
    int index = Index;

    int *backupElementsArray = (int*)malloc(sizeof(int) * (vector->Size - index));
    int backupElementsArrayIndex = 0;

    for (int i = index; i < vector->Size; i++)
    {
        backupElementsArray[backupElementsArrayIndex++] = vector->Elements[i];
    }

    *BackupElementsArray = backupElementsArray;
    return 0;
}

int VecReallocIfNeeded(CC_VECTOR *Vector)
{
    if (NULL == Vector)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;

    if (vector->Size > vector->Capacity)
    {
        vector->Capacity *= 2;
        int *temp = (int*)realloc(vector->Elements, vector->Capacity * sizeof(int));
        vector->Elements = temp;
    }

    Vector = vector;
    return 0;
}

int VecMergeSort(CC_VECTOR *Vector, int LeftIndex, int RightIndex)
{
    if (NULL == Vector || LeftIndex > RightIndex ||
        LeftIndex < 0 || RightIndex > Vector->Size - 1)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;
    int leftIndex = LeftIndex;
    int rightIndex = RightIndex;

    if (leftIndex == rightIndex) // nothing to sort
    {
        return 0;
    }

    int checkError = 0; // 0 if no error, otherwise we have an error

    int middleIndex = (rightIndex + leftIndex) / 2;
    checkError = VecMergeSort(vector, leftIndex, middleIndex);
    if (0 != checkError)
    {
        return -1;
    }
    checkError = VecMergeSort(vector, middleIndex + 1, rightIndex);
    if (0 != checkError)
    {
        return -1;
    }

    CC_VECTOR *auxVector = NULL;
    checkError = VecCreate(&auxVector);
    if (0 != checkError)
    {
        return -1;
    }

    int leftHalfIndex = leftIndex, rightHalfIndex = middleIndex + 1;

    while (leftHalfIndex <= middleIndex && rightHalfIndex <= rightIndex)
    {
        int leftElement = vector->Elements[leftHalfIndex];
        int rightElement = vector->Elements[rightHalfIndex];

        if (leftElement < rightElement)
        {
            checkError = VecInsertTail(auxVector, leftElement);
            if (0 != checkError)
            {
                return -1;
            }
            leftHalfIndex++;
        }
        else
        {
            checkError = VecInsertTail(auxVector, rightElement);
            if (0 != checkError)
            {
                return -1;
            }
            rightHalfIndex++;
        }
    }

    int remainingIndex, remainingUpperBound;
    if (rightHalfIndex > rightIndex)
    {
        remainingIndex = leftHalfIndex;
        remainingUpperBound = middleIndex;
    }
    else
    {
        remainingIndex = rightHalfIndex;
        remainingUpperBound = rightIndex;
    }

    for (int i = remainingIndex; i <= remainingUpperBound; i++)
    {
        checkError = VecInsertTail(auxVector, vector->Elements[i]);
        if (0 != checkError)
        {
            return -1;
        }
    }

    for (int i = leftIndex; i <= rightIndex; i++)
    {
        vector->Elements[i] = auxVector->Elements[i - leftIndex];
    }

    Vector = vector;
    return 0;
}

int VecCreate(CC_VECTOR **Vector)
{
    if (NULL != *Vector)
    {
        return -1;
    }

    *Vector = (CC_VECTOR*)malloc(sizeof(CC_VECTOR));
    (*Vector)->Capacity = 1;
    (*Vector)->Size = 0;
    (*Vector)->Elements = (int*)malloc(sizeof(int));

    return 0;
}

int VecDestroy(CC_VECTOR **Vector)
{
    free(*Vector);
    *Vector = NULL;

    return 0;
}


int VecInsertTail(CC_VECTOR *Vector, int Value)
{
    if (NULL == Vector)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;
    int value = Value;

    vector->Size++;
    if(0 != VecReallocIfNeeded(vector))
    {
        return -1;
    }
    vector->Elements[vector->Size - 1] = value;

    Vector = vector;
    return 0;
}

int VecInsertHead(CC_VECTOR *Vector, int Value)
{
    if (NULL == Vector)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;
    int value = Value;

    vector->Size++;
    if (0 != VecReallocIfNeeded(vector))
    {
        return -1;
    }

    for (int i = 1; i < vector->Size; i++)
    {
        vector->Elements[i] = vector->Elements[i - 1];
    }
    vector->Elements[0] = value;

    Vector = vector;
    return 0;
}

int VecInsertAfterIndex(CC_VECTOR *Vector, int Index, int Value)
{
    // can't insert after last element
    if (NULL == Vector || Index < 0 || Index >= Vector->Size - 1)
    {
         return -1;
    }

    CC_VECTOR *vector = Vector;
    int index = Index;
    int value = Value;

    int *backupElementsArray = NULL;

    int canBackup = VecBackupElementsIncludingIndex(vector, index + 1, &backupElementsArray);
    if (0 != canBackup)
    {
        perror("Can't backup");
        return -1;
    }

    vector->Elements[index + 1] = value;

    for (int i = index + 2; i < vector->Size; i++)
    {
        vector->Elements[i] = backupElementsArray[i - index - 2];
    }

    int canInsertTail = VecInsertTail(vector, backupElementsArray[vector->Size - index - 2]);
    if (0 != canInsertTail)
    {
        perror("Can't insert at tail");
        return -1;
    }

    Vector = vector;
    return 0;
}

int VecRemoveByIndex(CC_VECTOR *Vector, int Index)
{
    if (NULL == Vector || Index >= Vector->Size || Index < 0)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;
    int index = Index;

    for (int i = index; i < vector->Size - 1; i++)
    {
        vector->Elements[i] = vector->Elements[i + 1];
    }
    vector->Elements[--vector->Size] = 0;

    Vector = vector;
    return 0;
}

int VecGetValueByIndex(CC_VECTOR *Vector, int Index, int *Value)
{
    if (NULL == Vector || Index >= Vector->Size || Index < 0)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;
    int index = Index;
    int *value = Value;

    *value = vector->Elements[index];

    Vector = vector;
    Value = value;
    return 0;
}

int VecGetCount(CC_VECTOR *Vector)
{
    if (NULL == Vector)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;

    return vector->Size;
}

int VecClear(CC_VECTOR *Vector)
{
    if (NULL == Vector)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;

    vector->Size = 0;
    vector->Capacity = 1;
    int *temp = (int*)realloc(vector->Elements, sizeof(int));
    vector->Elements = temp;

    Vector = vector;
    return 0;
}

int VecSort(CC_VECTOR *Vector)
{
    if (NULL == Vector)
    {
        return -1;
    }

    CC_VECTOR *vector = Vector;

    int checkError = VecMergeSort(vector, 0, vector->Size - 1);
    if (0 != checkError)
    {
        return -1;
    }

    Vector = vector;
    return 0;
}