Challenge: Write Merge Sort

Lab C++ Intermediate 20 points

Sort n numbers with your own merge sort (no std::sort) and print them separated by spaces.

Input

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

Output

The sorted numbers.

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

C++

Hints

Base case: a range of 0 or 1 items.

Sort both halves, then merge with two pointers into a temporary vector.

Solution explanation

O(n log n) time, O(n) extra memory.

Show solution

#include <iostream>
#include <vector>
using namespace std;

void mergeSort(vector<int>& v, int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    mergeSort(v, lo, mid);
    mergeSort(v, mid, hi);
    vector<int> m;
    int i = lo, j = mid;
    while (i < mid && j < hi) m.push_back(v[i] <= v[j] ? v[i++] : v[j++]);
    while (i < mid) m.push_back(v[i++]);
    while (j < hi) m.push_back(v[j++]);
    for (int k = 0; k < (int)m.size(); k++) v[lo + k] = m[k];
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    mergeSort(v, 0, n);
    for (int i = 0; i < n; i++) cout << v[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Output

Answer