static int[] sort(int[] ar)
    {
        if(ar.length == 1)
            return ar;
        if(ar.length ==2)
        {
            if(ar[0] < ar[1])
                return ar;
            else
            {
                swap(ar,0,1);
                return ar;
            }
        }

        int[] h = new int[ar.length/2];
        int[] k = new int[ar.length-(ar.length/2)];

        for(int i = 0; i < ar.length/2; i++)
        {
            h[i] = ar[i];
        }

        int i = 0;
        for(int j = ar.length/2; j < ar.length; j++)
        {
            k[i] = ar[j];
            i++;
        }

        return merge(sort(h),sort(k));
    }


    static int[] swap(int[] a, int i, int j)
    {
        int v = a[i];
        a[i]=a[j];
        a[j]=v;
        return a;
    }