#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;
    VecDestroy(&auxVector);
    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)->Elements);
    (*Vector)->Elements = NULL;
    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;

}