归并排序是基于归并操作完成的，而一次归并操作是通过两个或两个以上的有序表合并成一个新的有序表完成的。常见的归并排序是2-路归并排序，其核心操作是将一维数组中前后相邻的两个有序序列归并成一个有序序列。其算法可以描述如下：
在本题中，读入一串整数，将其使用以上描述的2-路归并排序的方法从小到大排序，并输出。
2099: 算法10-12~10-14：归并排序
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $834$ | 正确数量 | $759$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 排序 |
Description
Input
输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过100000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。
Output
只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。
Sample Input复制
10
2 8 4 6 1 10 7 3 5 9
Sample Output复制
1 2 3 4 5 6 7 8 9 10
提示
在本题中，需要按照题目描述中的算法完成2-路归并排序的算法。
不难发现，2-路归并算法的时间复杂度为O(nlog2n)，且需要和原始数据等数量的辅助空间。递归形式的2-路归并排序算法在形式上比较简洁，但是实用性较差。通常在需要使用归并排序的场合，往往使用非递归形式的归并排序。
与快速排序和堆排序相比，归并排序的特点在于其是一种稳定的排序方法。
推荐代码 查看2099 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$16 $ms] | 2701170339 | 278751 | 2018-09-27 09:58:26 |
| 内存最少[$1384 $KB] | 悠悠兔 | 692831 | 2020-12-29 00:20:27 |
| 第一AC | 范晋豪@信息与计算科学142 | 152776 | 2017-11-16 15:10:18 |
| 第一挑战 | 范晋豪@信息与计算科学142 | 152776 | 2017-11-16 15:10:18 |
赛题来源/所属竞赛 数据结构高分笔记 数据结构高分笔记
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|---|---|---|
| 1799 | 2023-2024-2学期<计算机专业竞赛实训> 第3周练习：递归分治、高级排序和贪心算法【22计算机】 | 2024-03-11 00:00:00 | 请登录 |
| 1739 | 2022-2023-2学期<计算机专业竞赛实训> 第5周练习：递归分治、高级排序和贪心算法【21计算机12345】 | 2023-03-20 00:00:00 | 请登录 |
| 1682 | 2021-2022-2学期<算法分析与设计> 第3周练习：递归和基础排序 | 2022-03-07 08:00:00 | 请登录 |
| 1637 | 2021信息学/ACM集训（一）-排序和查找 | 2021-04-03 09:00:00 | 请登录 |
| 1608 | 2020-2021-2学期<算法分析与设计>第4周练习：排序算法 | 2021-03-15 08:00:00 | 请登录 |