1. #include <iostream>
2. using namespace std;
3. int b[10000001];
4. void swap(int &a, int &b)
5. {
6.     int temp = a;
7.     a = b;
8.     b = temp;
9. }
10. void bubble_sort(int *arr, int n)
11. {
12.     for (int i = n - 1; i >= 1; i--)
13.     {
14.         for (int j = 0; j < i; j++)
15.         {
16.             if (arr[j] > arr[j + 1])
17.                 swap(arr[j], arr[j + 1]);
18.         }
19.     }
20. }
21. void insertion_sort(int *arr, int n)
22. {
23.     for (int i = 1; i < n; i++)
24.     {
25.         for (int j = i; j >= 1; j--)
26.         {
27.             if (arr[j] < arr[j - 1])
28.  
29.                 swap(arr[j], arr[j - 1]);
30.         }
31.     }
32. }
33. void selection_sort(int *arr, int n)
34. {
35.     for (int i = 0; i < n - 1; i++)
36.     {
37.         int mini = i;
38.         for (int j = i; j < n; j++)
39.         {
40.             if (arr[j] < arr[mini])
41.                 mini = j;
42.         }
43.         swap(arr[i], arr[mini]);
44.     }
45. }
46. void counting_sort(int *arr, int n)
47. {
48.     int maximum = arr[0];
49.     for (int i = 1; i < n; i++)
50.     {
51.         if (arr[i] > maximum)
52.             maximum = arr[i];
53.     }
54.     int ind = 0;
55.     int size = maximum + 1;
56.     int count[size];
57.     for (int i = 0; i < size; i++)
58.         count[i] = 0;
59.     for (int i = 0; i < n; i++)
60.         count[arr[i]]++;
61.     for (int i = 0; i < size; i++)
62.     {
63.         while (count[i])
64.         {
65.             arr[ind++] = i;
66.             count[i]--;
67.         }
68.     }
69. }
70. void merge(int *arr, int lo, int mid, int hi)
71. {
72.     int curr1 = lo, curr2 = mid + 1;
73.     int ind = lo;
74.     while (curr1 <= mid && curr2 <= hi)
75.     {
76.         if (arr[curr1] > arr[curr2])
77.             b[ind++] = arr[curr2++];
78.         else
79.             b[ind++] = arr[curr1++];
80.     }
81.     while (curr1 <= mid)
82.         b[ind++] = arr[curr1++];
83.     while (curr2 <= hi)
84.         b[ind++] = arr[curr2++];
85.     for (int i = lo; i <= hi; i++)
86.         arr[i] = b[i];
87. }
88. void merge_sort(int *arr, int lo, int hi)
89. {
90.     if (lo == hi)
91.         return;
92.     int mid = (lo + hi) / 2;
93.     merge_sort(arr, lo, mid);
94.     merge_sort(arr, mid + 1, hi);
95.     merge(arr, lo, mid, hi);
96. }
97. void countsort(int *arr,int n,int pos){
98.       int count[10]={};
99.       for(int i = 0;i<n;i++)
100.        count[(arr[i]/pos)]++;
101.       for(int i = 1;i<10;i++)
102.        count[i]+=count[i-1];
103.       for(int i=n-1;i>=0;i--)
104.        b[--count[(arr[i]/pos)]]=arr[i];
105.       for(int i=0;i<n;i++)
106.        arr[i]=b[i];
107.  
108. }
109. void radix_sort(int *arr,int n){
110.     int maxi = arr[0];
111.     for(int i=0;i<n;i++)
112.     if(arr[i]>maxi)maxi=arr[i];
113.     for(int pos=1;(maxi/pos)>0;pos*=10){
114.         countsort(arr,n,pos);
115.     }
116. }
117. int main()
118. {
119.     int n;
120.     cin >> n;
121.     int arr[n];
122.     for (int i = 0; i < n; i++)
123.         cin >> arr[i];
124.     // bubble_sort(arr,n);
125.     // insertion_sort(arr,n);
126.     // selection_sort(arr,n);
127.     // counting_sort(arr,n);
128.     // merge_sort(arr,0,n-1);
129.     // radix_sort(arr,n);
130.     for (int i = 0; i < n; i++)
131.         cout << arr[i] << " ";
132.     cout << endl;
133. }