Challenge: Write Merge Sort

Lab Java Intermediate 20 points

Sort the numbers with your own merge sort (no Arrays.sort) and print them.

Input

Line 1: n. Line 2: n whole numbers.

Output

The sorted numbers, separated by spaces.

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

mergeSort(a, lo, hi): stop when lo >= hi, otherwise sort both halves and merge.

Merge into a temporary array, then copy it back into a[lo..hi].

Solution explanation

log n levels of splitting, O(n) merging per level: O(n log n) time, O(n) extra memory.

Show solution

import java.util.Scanner;

public class Main {
    static void mergeSort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        int[] tmp = new int[hi - lo + 1];
        int i = lo, j = mid + 1, k = 0;
        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 = 0; k < tmp.length; k++) a[lo + 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, 0, n - 1);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(a[i]);
        System.out.println(sb);
    }
}

Output

Answer