1648: 归并排序

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：49 Solved：37

Description

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代；

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

2. 算法步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

  4. 重复步骤 3 直到某一指针达到序列尾；

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

3. 动图演示




【以上内容来源： https://www.runoob.com/w3cnote/merge-sort.html 】



【题目描述】

输入一个序列，使用归并排序法，完成排序。

Input

第一行，输入n，表示n个数字。
第2~n+1行，一行输入一个整数。

Output

按照升序排好序的序列，用空格分隔。

Sample Input Copy 

5
3
1
2
5
4

Sample Output Copy 

1 2 3 4 5

HINT

自己实现归并排序，不要使用系统现成的排序函数，或者其他排序方法完成。