4544 - Merge sort (Challenge)

• Submit
• Status
• Discuss
• Summary

Description

합병 정렬 또는 병합 정렬(merge sort)은 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.

합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

Merge sort로 정렬한 결과와 재귀함수 실행 횟수를 구해보자.

어떻게 나눠도 상관 없지만 이 문제에서는 배열의 길이가 홀수인 경우 배열의 첫 번째 요소부터 (배열의 길이-1)/2번째 요소까지, (배열의 길이+1)/2번째 요소부터 (배열의 길이)번째 요소까지 두 개로 나눈다.

Input

* Line 1 : 정렬할 배열 갯수 N (1≤N≤1000)

* Line 2~N+1 : 배열 arr의 크기 n이 입력되고 그 뒤로 배열 arr의 원소들이 공백으로 구분되어 입력된다. (1 ≤ n ≤ 100, -2000 ≤ arr[i] ≤ 2000)

Output

* Line 1~N : 정렬 중의 재귀함수 실행 횟수와 정렬 결과를 공백으로 구분하여 한 줄로 출력한다.

Sample Input

3
3 0 2 1
4 4 3 2 1
7 1 5 3 3 2 6 4

Sample Output

5 0 1 2
7 1 2 3 4
13 1 2 3 3 4 5 6

Hint

1회: {1, 5, 3, 3, 2, 6, 4} -> {1, 5, 3}{3, 2, 6, 4}

    2회: {1, 5, 3} -> {1}{5, 3}

        3회: {1}

        4회: {5, 3} -> {5}{3}

            5회: {5}

            6회: {3}

        -> {5}{3} -> {3, 5}

    -> {1}{3, 5} -> {1, 3, 5}

    7회: {3, 2, 6, 4} -> {3, 2}{6, 4}

        8회: {3, 2} -> {3}{2}

            9회: {3}

            10회:{2}

        -> {3}{2} -> {2, 3}

        11회: {6, 4} ->{6}{4}

            12회: {6}

            13회: {4}

        -> {4, 6}

    -> {2, 3}{4, 6}->{2, 3, 4, 6}

-> {1, 3, 5}{2, 3, 4, 6}->{1, 2, 3, 3, 4, 5, 6}