分治与减治算法实验：题目2 排序中分治法的程序设计

题目描述：

请设计一个使用分治算法实现排序的程序，可以对任意长度的整数数组进行排序。

输入格式：

第一行输入一个整数 n，表示数组长度。

第二行输入 n 个整数，表示待排序的数组。

输出格式：

输出 n 个整数，表示排序后的数组。

样例：

输入：

10
3 1 4 1 5 9 2 6 5 3

输出：

1 1 2 3 3 4 5 5 6 9

算法思路：

分治算法的基本思路是将问题分解成若干个子问题，分别解决这些子问题，然后将子问题的解组合起来得到原问题的解。排序也是分治算法的一个经典应用，我们可以将待排序数组分成两个子数组，分别进行排序，然后合并两个有序子数组得到有序数组。

具体实现时，我们可以选择归并排序算法，它的时间复杂度为 O(nlogn)。

程序实现时，我们首先定义一个归并排序函数 merge_sort，它接收一个整数数组 arr 和数组长度 n，返回一个排好序的数组。在 merge_sort 函数中，我们先判断数组是否只有一个元素，如果是，直接返回该数组；否则，将数组分成两个子数组，分别进行排序，然后将两个有序子数组合并成一个有序数组。

代码实现：