Table of Contents

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;
}
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on pinterest
Pinterest
Share on whatsapp
WhatsApp
Share on email
Email
Md. Nurnobi Hosen
Md. Nurnobi Hosen

Student of Computer Science and Engineering at Daffodil International University,Main Campus ,Dhanmondi.
Web and App Developer also expart of wordpress customization

All Blog Posts »
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x