Problem 2664 --Recursion / Divide and Conquer - Merge Sort

2664: Recursion / Divide and Conquer - Merge Sort

上一题 正确率: $56.10\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $41$ 正确数量 $23$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL

Description

Merge Sort 

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.

    Merge(A, left, mid, right)

      n1 = mid - left; 

      n2 = right - mid;

      create array L[0...n1], R[0...n2]

      for i = 0 to n1-1 

        do L[i] = A[left + i] 

      for i = 0 to n2-1 

         do R[i] = A[mid + i]

      L[n1] = SENTINEL 

      R[n2] = SENTINEL 

        i = 0; 

        j = 0;

       for k = left to right-1 

            if L[i] <= R[j] 

             then A[k] = L[i] 

                 i = i + 1 

             else A[k] = R[j] 

                  j = j + 1

      Merge-Sort(A, left, right){

         if left+1 < right 

         then mid = (left + right)/2;

         call Merge-Sort(A, left, mid) 

         call Merge-Sort(A, mid, right)

         call Merge(A, left, mid, right)

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.

Sample Input复制

10
8 5 9 2 6 3 7 1 10 4

Sample Output复制

1 2 3 4 5 6 7 8 9 10
34

提示

n ≤ 500000 

0 ≤ an element in S ≤ 10^9

推荐代码 查看2664 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] soul 650043 2020-11-08 16:31:49
内存最少[$0 $KB] ZZZZZZ 608261 2020-07-24 09:22:28
第一AC 土豆宝 294085 2018-10-24 12:32:07
第一挑战 AOJ大管家 294081 2018-10-24 12:30:13

赛题来源/所属竞赛 会津大学《挑战数据结构与算法》 挑战数据结构与算法

竞赛编号 竞赛名称 竞赛时间 访问比赛
1528 2020年《图灵信息学算法》第一单元：排序和查找 2020-07-19 14:30:00 请登录
1211 庆祝2018年10.24世界程序员节日欢乐AC赛(竞赛密码6的二进制)~ 2018-10-24 10:24:00 请登录