#include <iostream>
using namespace std;
 
//Bài này nếu dùng mảng đánh dấu, tôi sẽ đạt đc độ phức tạp yêu cầu là 3n
//Đối với những bài toán sắp xếp, nếu giá trị các phần tử trong mảng không quá cao(phải là số lớn hơn 0), mà số lượng
//các phần tử lớn, bản thân mình thấy dùng mảng đánh dấu là NO.1 :), ý kiến cá nhân thôi
 
int main() {
 
	//Khai báo mảng a, khai báo cứng cho nhanh, mảng a có 10 phần tử
	int a[10] = {11, 1, 6, 3, 5, 2, 7, 9, 8, 4};
 
	//Khai báo mảng đánh dấu( độ dài mảng = max(a[i]), nghĩa là bằng với giá trị
	//cao nhất của 1 phần tử nào đó trong mảng n. Khai báo mảng b và khởi tạo mọi
	//giá trị trong mảng  = 0
	int b[10000+1] = {};
 
	//Chạy 1 vòng lặp mất O(n) để đánh dấu
	for(int i = 0; i < 10; i++){
		b[a[i]]++;
	}
 
	//Chạy vòng lặp mất m + n để lưu lại giá trị vào mảng a
	//Ở đây m < n rất nhiều, nên tổng chi phí 2 vòng for trên chưa vượt quá 3n.
	//Dùng mẹo đơn giản :)
	int dem = 0;
	for(int j = 0; j <= 10000; j++){
		while(b[j] > 0){
			a[dem] = j;	
			b[j]--;
			dem++;
		}
	}
 
	//In lại để kiểm tra mảng đã sắp xếp
	for(int i = 0; i < 10; i++){
		cout << a[i] << " ";
	}
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy9Cw6BpIG7DoHkgbuG6v3UgZMO5bmcgbeG6o25nIMSRw6FuaCBk4bqldSwgdMO0aSBz4bq9IMSR4bqhdCDEkWMgxJHhu5kgcGjhu6ljIHThuqFwIHnDqnUgY+G6p3UgbMOgIDNuCi8vxJDhu5FpIHbhu5tpIG5o4buvbmcgYsOgaSB0b8OhbiBz4bqvcCB44bq/cCwgbuG6v3UgZ2nDoSB0cuG7iyBjw6FjIHBo4bqnbiB04butIHRyb25nIG3huqNuZyBraMO0bmcgcXXDoSBjYW8ocGjhuqNpIGzDoCBz4buRIGzhu5tuIGjGoW4gMCksIG3DoCBz4buRIGzGsOG7o25nCi8vY8OhYyBwaOG6p24gdOG7rSBs4bubbiwgYuG6o24gdGjDom4gbcOsbmggdGjhuqV5IGTDuW5nIG3huqNuZyDEkcOhbmggZOG6pXUgbMOgIE5PLjEgOiksIMO9IGtp4bq/biBjw6EgbmjDom4gdGjDtGkKCmludCBtYWluKCkgewoKCS8vS2hhaSBiw6FvIG3huqNuZyBhLCBraGFpIGLDoW8gY+G7qW5nIGNobyBuaGFuaCwgbeG6o25nIGEgY8OzIDEwIHBo4bqnbiB04butCglpbnQgYVsxMF0gPSB7MTEsIDEsIDYsIDMsIDUsIDIsIDcsIDksIDgsIDR9OwoJCgkvL0toYWkgYsOhbyBt4bqjbmcgxJHDoW5oIGThuqV1KCDEkeG7mSBkw6BpIG3huqNuZyA9IG1heChhW2ldKSwgbmdoxKlhIGzDoCBi4bqxbmcgduG7m2kgZ2nDoSB0cuG7iwoJLy9jYW8gbmjhuqV0IGPhu6dhIDEgcGjhuqduIHThu60gbsOgbyDEkcOzIHRyb25nIG3huqNuZyBuLiBLaGFpIGLDoW8gbeG6o25nIGIgdsOgIGto4bufaSB04bqhbyBt4buNaQoJLy9nacOhIHRy4buLIHRyb25nIG3huqNuZyAgPSAwCglpbnQgYlsxMDAwMCsxXSA9IHt9OwoJCgkvL0No4bqheSAxIHbDsm5nIGzhurdwIG3huqV0IE8obikgxJHhu4MgxJHDoW5oIGThuqV1Cglmb3IoaW50IGkgPSAwOyBpIDwgMTA7IGkrKyl7CgkJYlthW2ldXSsrOwoJfQoJCgkvL0No4bqheSB2w7JuZyBs4bq3cCBt4bqldCBtICsgbiDEkeG7gyBsxrB1IGzhuqFpIGdpw6EgdHLhu4sgdsOgbyBt4bqjbmcgYQoJLy/hu54gxJHDonkgbSA8IG4gcuG6pXQgbmhp4buBdSwgbsOqbiB04buVbmcgY2hpIHBow60gMiB2w7JuZyBmb3IgdHLDqm4gY2jGsGEgdsaw4bujdCBxdcOhIDNuLgoJLy9Ew7luZyBt4bq5byDEkcahbiBnaeG6o24gOikKCWludCBkZW0gPSAwOwoJZm9yKGludCBqID0gMDsgaiA8PSAxMDAwMDsgaisrKXsKCQl3aGlsZShiW2pdID4gMCl7CgkJCWFbZGVtXSA9IGo7CQoJCQliW2pdLS07CgkJCWRlbSsrOwoJCX0KCX0KCQoJLy9JbiBs4bqhaSDEkeG7gyBraeG7g20gdHJhIG3huqNuZyDEkcOjIHPhuq9wIHjhur9wCglmb3IoaW50IGkgPSAwOyBpIDwgMTA7IGkrKyl7CgkJY291dCA8PCBhW2ldIDw8ICIgIjsKCX0KCQkKCXJldHVybiAwOwp9