• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

Merge Sort

AOJ 站点默认 6个月前 (04-11) 262次浏览 已收录 0个评论
文章目录[隐藏]

Question

Write a program of a Merge Sort algorithm implemented by the following pseudocode. You should also report the number of comparisons in the Merge function.

Input
In the first line n is given. In the second line, n integers are given.

Output
In the first line, print the sequence S. Two consequtive elements should be separated by a space character.

In the second line, print the number of comparisons.

Constraints
n ≤ 500000
0 ≤ an element in S ≤ 109
Sample Input 1
10
8 5 9 2 6 3 7 1 10 4
Sample Output 1
1 2 3 4 5 6 7 8 9 10
34

Meaning


实现归并排序,除了输出排序后的数组,下一行输出归并排序在比较过程中的次数

Sloution

归并排序利用了分治的思想,首先先分,给数组全部对半分开,分开后分到不能再分,这时候需要合并,写一个合并函数将其合并

Coding

Summary


归并排序的总体复杂度为0(nlogn)

个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Merge Sort
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到