import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void merge(int[] arr,int low,int mid,int high){
        int i=low;
        int j=mid+1;
        int k=0;
        int n=high-low+1;
        int[] new_arr=new int[n];
        while((i<=mid) && (j<=high)){
            if(arr[i]<arr[j]){
                new_arr[k]=arr[i];
                i++;
            }else{
                new_arr[k]=arr[j];
                j++;
            }
            k++;
        }
        while(i<=mid){
            new_arr[k]=arr[i];
            i++;
            k++;
        }
        while(j<=high){
            new_arr[k]=arr[j];
            j++;
            k++;
        }
        for(int c=0;c<n;c++){
            arr[low+c]=new_arr[c];
        }
    }
    public static void merge_sort(int[] arr,int low,int high){
        if(low==high) return;
        int mid=(low+high)/2;
        merge_sort(arr,low,mid);
        merge_sort(arr,mid+1,high);
        merge(arr,low,mid,high);
    }
    public static void main(String[] args) {
        int[] arr=new int[5];
        arr[0]=4;
        arr[1]=1;
        arr[2]=3;
        arr[3]=9;
        arr[4]=2;
        //int j=0;

        merge_sort(arr,0,4);
        for(int i=0;i<5;i++){
            System.out.println(arr[i]);
        }
    }
}