#include <iostream>
#include <string>
using namespace std;


void scal (string *array, int poczatek, int srodek, int koniec) {
    string* new_array = (string*)calloc(koniec-poczatek, sizeof(*array));
    int i = poczatek;
    int j = srodek+1;
    int k = 0;

    while (i <= srodek && j <= koniec) {
        if (array[j].size() < array[i].size()) {
            new_array[k] = array[j];
            j++;
        } else if (array[j].size() == array[i].size()) {
            for(int a=0; a<array[j].size(); a++) {
                if (array[j][a] > array[i][a]) {
                    new_array[k] = array[i];
                    i++;
                    break;
                } else if (array[j][a] < array[i][a]) {
                    new_array[k] = array[j];
                    j++;
                    break;
                } else if (a == array[j].size()-1) {
                    new_array[k] = array[j];
                    j++;
                    break;
                }
            }
        } else {
            new_array[k] = array[i];
            i++;
        }
        k++;
    }

    if (i <= srodek) {
        while (i <= srodek) {
            new_array[k] = array[i];
            i++;
            k++;
        }
    } else {
        while (j <= koniec) {
            new_array[k] = array[j];
            j++;
            k++;
        }
    }
    for (i = 0; i <= koniec-poczatek; i++) {
        array[poczatek+i] = new_array[i];
    }
    free(new_array);
}

void sortuj (string *array, int poczatek, int koniec) {
    if (poczatek == koniec) {
        return;
    } else {
        int srodek = (poczatek + koniec) / 2;
        sortuj(array, poczatek, srodek);
        sortuj(array, srodek+1, koniec);
        scal(array, poczatek, srodek, koniec);
    }
}

int main() {
    int N;
    printf("Wpisz ile liczb chcesz posortowac (N): ");
    scanf("%d", &N);

    //tworzenie tablicy
    string* array = (string*)calloc(N, sizeof(*array));

    //wczytywanie tablicy
    for(int i=0; i<N; i++) {
        cin >> array[i];
    }

    // sortowanie przez scalanie
    sortuj(array, 0, N-1);

    //wypisywanie tablicy
    for(int i=0; i<N; i++) {
        cout << array[i] << endl;
    }

    //zwolnienie tablicy
    free(array);
    return 0;
}