Merge Sort

Lab Java Advanced 30 points

Implement recursive merge sort and print the sorted array.

Input

n, then n integers.

Output

The sorted array.

Example

Input

7
38 27 43 3 9 82 10

Output

[3, 9, 10, 27, 38, 43, 82]

Sample input available Sample output available

Editor

Java

Hints

Sort each half, then merge the two sorted halves using a temporary array.

Solution explanation

Merge sort is O(n log n) and stable; Java uses a merge-sort variant (TimSort) for objects.

Show solution

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
        if (hi - lo < 1) return;
        int mid = (lo + hi) / 2;
        mergeSort(a, tmp, lo, mid);
        mergeSort(a, tmp, mid + 1, hi);
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= hi) tmp[k++] = a[j++];
        for (k = lo; k <= hi; k++) a[k] = tmp[k];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        mergeSort(a, new int[n], 0, n - 1);
        System.out.println(Arrays.toString(a));
    }
}

Output

Answer