import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
public static void sort(int[] arr) {
int[] tempArr = new int[arr.length];
split(arr, 0, arr.length - 1, tempArr);
}
private static void split(int[] arr, int left, int right, int[] tempArr) {
if (left == right) { // 当区间左边界等于有边界,说明区间内只有一个值, 此时不需要再进行拆分
return;
}
// 分
int mid = (left + right) >>> 1; // 使用无符号右移操作符进行算术除法,这能防止(left+right)的值超出int的范围而导致的报错,而在二进制中,一个数右移一位表示除以2;左移一位表示乘以2,比如在二进制下, 10到100乘以了2, 100到10就是除以了2
split(arr, left, mid, tempArr);
split(arr, mid + 1, right, tempArr);
// 合
merge(arr, left, mid, mid + 1, right, tempArr);
System.arraycopy(tempArr, left, arr, left, right - left + 1); //将临时数组中完成排序的元素按照对应位置更新原数组
}
/*
arr : 原始数组
i~iEnd: 第一个有序区间的范围
j~jEnd: 第二个有序区间的范围
tempArr: 临时数组,与arr的长度一致
*/
private static void merge(int[] arr, int i, int iEnd, int j, int jEnd, int[] tempArr) { // 非递归地实现
int k = i;
while (i <= iEnd && j <= jEnd) {
if (arr[i] < arr[j]) {
tempArr[k] = arr[i];
k++;
i++;
} else {
tempArr[k] = arr[j];
k++;
j++;
}
}
if (i <= iEnd) {
System.arraycopy(arr, i, tempArr, k, iEnd - i + 1);
}
if (j <= jEnd) {
System.arraycopy(arr, j, tempArr, k, jEnd - j + 1);
}
}
/*
arr : 原始数组
i~iEnd: 第一个有序区间的范围
j~jEnd: 第二个有序区间的范围
tempArr: 临时数组,与arr的长度一致
*/
private static void merge(int[] arr, int i, int iEnd, int j, int jEnd, int[] tempArr, int k) { // 递归地实现
//递归结束条件:
if (i > iEnd) {
if (j <= jEnd) {
System.arraycopy(arr, j, tempArr, k, jEnd - j + 1); // 被复制数组; 被复制起点索引; 目标数组; 目标数组起点索引; 复制元素的个数
return;
}
}
if (j > jEnd) {
if (i <= iEnd) {
System.arraycopy(arr, i, tempArr, k, iEnd - i + 1); // 被复制数组; 被复制起点索引; 目标数组; 目标数组起点索引; 复制元素的个数
return;
}
}
// 递归
if (arr[i] < arr[j]) {
tempArr[k] = arr[i];
merge(arr, i + 1, iEnd, j, jEnd, tempArr, k + 1);
} else {
tempArr[k] = arr[j];
merge(arr, i, iEnd, j + 1, jEnd, tempArr, k + 1);
}
}
public static void main(String[] args) throws IOException {
// 读取数组长度+数据
int length = Integer.parseInt(reader.readLine().strip());
String[] inputs = reader.readLine().split(" ");
reader.close();
int[] array = new int[length];
for (int i = 0; i < length; i++) {
if (inputs[i] != null) {
array[i] = Integer.parseInt(inputs[i]);
}
}
//排序并打印排序后结果
sort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + (i < array.length - 1 ? " " : ""));
}
}
}