Ở đây mình chỉ giới thiệu những thuật toán sắp xếp $O(n)$ vì hàm $std::sort$ trong c++ có độ phức tạp $O(nlog(n))$ rồi, cho nên bình thường ta sẽ sài hàm sort, chỉ một số trường hợp yêu cầu độ phức tạp $O(n)$ ta mới sài thuật toán dưới đây

**Counting sort (**Dành cho giá trị trong mảng bé thường là bé hơn $10^7$)

void CountingSort(vector<int>& arr)
{
	int max = *max_element(arr.begin(), arr.end());
	int min = *min_element(arr.begin(), arr.end());
	int range = max - min + 1;
	vector<int> count(range), out(arr.size());
	for(int i=0; i<arr.size(); i++) count[arr[i] - min]++;
	for(int i=1; i<count.size(); i++) count[i] += count[i-1];
	for(int i=arr.size()-1; i>-1; i--)
	{
		out[count[arr[i] - min] - 1] = arr[i];
		count[arr[i]-min]--;
	}
	for(int i=0; i<arr.size(); i++) arr[i] = out[i];
}