Age Sort UVA – 11462 | Solution

You are given the ages (in years) of all people of a country with at least 1 year of age. You know that no individual in that country lives for 100 or more years. Now, you are given a very simple task of sorting all the ages in ascending order.

Input

There are multiple test cases in the input file. Each case starts with an integer n (0 < n ≤ 2000000), the total number of people. In the next line, there are n integers indicating the ages. Input is terminated with a case where n = 0. This case should not be processed.

Output

For each case, print a line with n space separated integers. These integers are the ages of that country sorted in ascending order. Warning: Input Data is pretty big (∼ 25 MB) so use faster IO.

Sample Input

5 3 4 2 1 5 5 2 3 2 3 1 0

Sample Output

1 2 3 4 5 1 2 2 3 3

Solution Code

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

using namespace std;
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;


    int L[n1], R[n2];


    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];


    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }


    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}


void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {

        int m = l+(r-l)/2;

        
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}


void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++) {
if(i>0) printf(" ");
        printf("%d", A[i]);
}
printf("\n");
}


int main()
{
    int n,i;
    while(scanf("%d",&n) && n)
    {

        int arr[n];

        for( i=0; i<n; i++)
        {

            scanf("%d",&arr[i]);
        }



        mergeSort(arr, 0, n - 1);


        printArray(arr, n);

    }



    return 0;
}