80分求调

思路：将数组变成n个有序数组，然后并归。

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

vector<int> sort(vector<int> &need) {
	vector<vector<int >>all;
	vector<int> new_;
	vector<vector<int >> new_int;
	for(int i = 0; i<need.size(); i++) {
		if(all.size() == 0) {
			all.push_back(vector<int>{need[i]});
			continue;
		}
		bool end_ = false;
		for (int j = 0; j < all.size(); j++) {
			if (all[j][all[j].size() - 1] <= need[i]) {
				all[j].push_back(need[i]);
				end_ = true;
				break;
			}/*else if(all[j][0]>=need[i]){
			new_={};
			new_.push_back(need[i]);
			for(int p=0;p<all[j].size();p++){
			new_.push_back(all[j][p]);
			}
			all[j]=new_;
			end_=true;
			break;
			}*/
		}
		if (end_) {
			continue;
		} else {
			new_={};
			new_.push_back(need.at(i));
			all.push_back(new_);
			continue;
		}
	}
	while (all.size() != 1) {
		vector<int> a = all[all.size() - 1];
		vector<int> b = all[all.size() - 2];
		all.pop_back();
		all.pop_back();
		vector<int> ands;
		for (int i = 0, j = 0;;) {
			if (a.size() <= i && b.size() <= j) {
				break;
			} else if (a.size() <= i && b.size() >= j) {
				ands.push_back(b[j]);
				++j;
			} else if (a.size() >= i && b.size() <= j) {
				ands.push_back(a[i]);
				++i;
			} else {
				if (a[i] <= b[j]) {
					ands.push_back(a[i]);
					++i;
				} else {
					ands.push_back(b[j]);
					++j;
				}
			}
		}
		new_int={};
		new_int.push_back(ands);
		for(int i = 0; i<all.size(); i++) {
			new_int.push_back(all[i]);
		}
		all = new_int;
	}
	return all[0];
}

int main() {
	int a;
	vector<int> all;
	cin >> a;
	for (int i = 0; all.size() < a && cin >> i;) {
		all.push_back(i);
	}
	all = sort(all);
	for (int i = 0; i < all.size(); i++) {
		cout << all[i] << " ";
	}
}