• 欢迎访问废江网站,承蒙遇见 QQ群
  • 本站将致力于推送优质的java知识以及算法,开源代码!

Merge Sort

AOJ 站点默认 4年前 (2020-04-11) 4041次浏览 已收录 34个评论 扫描二维码
文章目录[隐藏]

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)
发表我的评论
取消评论

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

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址