Merge Sort

Lab C Advanced 30 points

Implement recursive merge sort with a temporary array and print the sorted array.

Input

Line 1: n. Line 2: n integers.

Output

One line.

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

Hints

Sort each half, then merge them into tmp and copy back.

Solution explanation

Merge sort is always O(n log n) and stable.

Show solution

#include <stdio.h>

int tmp[100];

void merge_sort(int *a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    merge_sort(a, lo, mid);
    merge_sort(a, mid + 1, hi);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) { tmp[k] = a[i]; i++; }
        else { tmp[k] = a[j]; j++; }
        k++;
    }
    while (i <= mid) { tmp[k] = a[i]; i++; k++; }
    while (j <= hi) { tmp[k] = a[j]; j++; k++; }
    for (k = lo; k <= hi; k++) a[k] = tmp[k];
}

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d%s", a[i], i < n - 1 ? " " : "\n");
    return 0;
}

Output

Answer