Codechef -> Practice -> Easy -> TurboSort

Problem Link : http://www.codechef.com/problems/TSORT

Solution :

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.PrintWriter;

import java.util.ArrayList;

/**

 *

 * @author XCoder

 */

class Turbo_MergeSort {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static PrintWriter pw = new PrintWriter(System.out);

    public static int readIntLine() throws IOException {

        return Integer.parseInt(br.readLine());

    }

    public static void main(String[] args) throws IOException {

//        int a[] = {2, 4, 6, 1, 3, 5, 4, 45, 1, 23, 6, 23, 43, 756, 2};

//        int test = readIntLine();

//        while (test-- > 0) {

            int arrsize = readIntLine();

            int index = 0;

            int a[] = new int[arrsize];

            while (arrsize-- > 0) {

                a[index++] = readIntLine();

            }

            MergeSort(a, 0, a.length - 1);

            for (int x : a) {

                pw.println(x);

            }

            pw.flush();

//        }

    }

    public static void MergeSort(int a[], int start, int end) {

        if (start == end) {

            return;

        }

        int mid = end + start;

        mid /= 2;

//        System.out.println("start " + start + "   mid : " + mid + "    end : " + end);

        MergeSort(a, start, mid);

        MergeSort(a, mid + 1, end);

//        System.out.println("merge occured");

        merge(a, start, mid, end);

    }

    public static void merge(int a[], int start, int mid, int end) {

        int first[] = new int[mid - start + 1];

        int second[] = new int[end - mid];

        int result[] = new int[end - start + 1];

        for (int i = 0; i < first.length; i++) {

            first[i] = a[start + i];

        }

        for (int i = 0; i < second.length; i++) {

            second[i] = a[mid + i + 1];

        }

        int indexresult = 0;

        int total = result.length;

        int indexi = 0;

        int indexj = 0;

        while (indexi < first.length && indexj < second.length) {

            if (first[indexi] < second[indexj]) {

                result[indexresult++] = first[indexi++];

            } else {

                result[indexresult++] = second[indexj++];

            }

        }

        while (indexi < first.length) {

            result[indexresult++] = first[indexi++];

        }

        while (indexj < second.length) {

            result[indexresult++] = second[indexj++];

        }

//        System.out.println("answer see here");

        for (int i = 0; i < result.length; i++) {

            a[start + i] = result[i];

//            System.out.println(a[start + i]);

        }

    }

}