# 3.1.1. Merge Sort

# 1. Merge Sort

Problem: Sort n keys in nondecreasing sequence.
Inputs: positive integer n, array of keys S indexed from 1 to n.
Outputs: the array S containing the keys in nondecreasing order. 배열 S는 감소하지 않는 순서로 정렬된 key를 갖는다
1. Divide the array into two subarrays each with ~$ \frac n 2$ items.
2. Conquer each subarray by sorting it recursively.
3. Combine the solutions to the subarrays by merging them into a single sorted array.

A simple implementation

// Sort a list from A[left] to A[right].
// Should be optimized for higher efficiency!!!

void merge_sort(item_type *A, int left, int right){
    int middle;
    if (left < right){
        //divide : O(1)
        middle = (left + right) / 2;            					
        //conquer : 2T(n/2)
        merge_sort(A, left, middle);
        merge_sort(A, middle + 1, right);
        //combine : O(n)
        merge(A, left, middle, right);
    }
}

item_type *buffer; 
// extra space for merge sort, allocated beforehand

void merge(item_type *A, int left, int middle, int right){
    int i, i_left, i_right;
    memcpy(buffer + left, A + left, sizeof(item_type) * (right - left + 1));
    //O(r-l+1), O(n)
    i_left = left;
    i_right = middle + 1;
    i = left;

    while ((i_left <= middle) && (i_right <= right)){
        if (buffer[i_left] < buffer[i_right])
            A[i++] = buffer[i_left++];
        else
            A[i++] = buffer[i_right++];
    }
    while (i_left <= middle)
        A[i++] = buffer[i_left++];
    while (i_right <= right)
        A[i++] = buffer[i_right++];
}

An example of merging two arrays

k	left	right	merged
1	10 12 20 27	13 15 22 25	10
2	10 12 20 27	13 15 22 25	10 12
3	10 12 20 27	13 15 22 25	10 12 13
4	10 12 20 27	13 15 22 25	10 12 13 15
5	10 12 20 27	13 15 22 25	10 12 13 15 20
6	10 12 20 27	13 15 22 25	10 12 13 15 20 22
7	10 12 20 27	13 15 22 25	10 12 13 15 20 22 25
-			10 12 13 15 20 22 25 27

# Worst-case time complexity

편의상 $n=2m$이라 할 경우 (m \in Z^+ \cup \{0\}
- T(n) = 2T(\frac {n} {2}) + cn, n \geq 2
  - 2 : Number of subproblems
  - \frac n 2 : Subproblem size
- T(1) =1 \rightarrow T(n) = O(nlogn)
- Merge Sort Complexity Analysis | Merge Sort | | | | ---------- | --------------- | ------- | | Divide | Conquer | Combine | | O(1) | 2T(\frac n 2) | O(n) |
n개의 원소를 $k$개와 $l$개로 나누어 진행한다고 가정하면 (n=k+l),
- T(n) = T(k) + T(l) + cn (k \approx l)
- n = 2^m 이 아닌 일반적인 경우에도 같은 시간 복잡도를 가짐을 증명할 수 있음.

# Solving Recurrence Equations

Solve the following recurrences T(n) for given T(1)=1
1. T(n) = aT(n-1) + bn
2. T(n) = T(\frac n 2) + bn \log n
3. T(n) = aT(n-1) + bn^2
4. T(n) = aT(n/2) + bn^2
5. T(n) = T(\frac n 2) + c \log n
6. T(n) = T(\frac n 2) + cn
7. T(n) = 2T(\frac n 2) + cn
8. T(n) = 2T(\frac n 2) + cn \log n
9. T(n) = T(n-1) + T(n-2), for T(1) = T(2) = 1

# Some Derivations

T(n) = 2 T(n/2) + cn, T(1) = 1
- assume n=2^m, i.e., m = log_2 m for some m \geq 0, m \in \mathbb{Z}
- T(2^m) = 2T(2^{m-1})+c \cdot 2^m \\= 2 \{2T(2^{m-2})+c \cdot 2^{m-1} \}+c \cdot 2^m \\=2^2 \cdot T(2^{m-2})+2 \cdot c \cdot 2^m \\= 2^2 \{2 \cdot T(2^{m-3})+c \cdot 2^{m-2} \}+2 \cdot c \cdot 2^m $\ ... \= 2^{m \cdot T(2}0) + m \cdot c \cdot 2^m $ \\= n \cdot 1 + (log_2 n) \cdot c \cdot n = O(n \log n )
T(n) = T(n-1) + cn, T(1) = 1
T(n) = 2 T(n/2) + cn^2, T(1) = 1
- Assume n=2^m for some m \in \mathbb{Z} - \mathbb {Z^-}
- 2 \cdot T (2^{m-1}) + c \cdot 2 ^2m $\ = 2 { 2 \cdot T(2^) + c \cdot 2 ^{{2(m-1)} } + c \cdot 2 ^{2m $
  $\= 2}2 \cdot T(2}) + c { 2^{2m-1} + 2 ^{{2m}} $
  $\ = 2 { 2 \cdot T(2}) + c \cdot 2 ^{{2(m-2)} } + c { 2}{2m-1} + 2^{2m} } $ $\= 2^{3 \cdot T(2})+ c { 2^{2m-2} + 2^{2m-1} + 2 ^{2m}} $ \\ … \\= 2^m + 2 \cdot c \cdot 2^{2m} - 2 \cdot c \cdot 2^m \\ =2 \cdot c \cdot n^2 - (2 \cdot c -1) n = O(n^2)

# Another Implementation of Merge Sort

ref. [Horowitz 7.6.3]

int rmerge(element list[], int lower, int upper){
/*sort the list, list[lower], ..., list[upper]. the link field in each record is initially set to -1*/
// list[lower], …, list[upper]까지 오름차순으로 정렬.
// 각 레코드의 link filed는 초기에 -1로 설정
  int middle;
  if (lower >= upper) return lower;
  else{
    middle = (lower + upper)/2;
    return listmerge(list, rmerge(list,lower,middle), rmerge(list, middle+1, upper));
  }
}

rmerge returns an integer that points to the start of the sorted list. start = rmerge(list, 0, n-1);

typedef struct {
  int key;
  int link;
} element;

int listmerge (element list[ ], int first, int second){
// first와 second가 가리키는 서브리스트들을 합병
  int start = n;
  while (first != -1 && second != -1) {
    if (list[first].key <= list[second].key) {
      list[start].link = first; 
      start = first;
      first = list[first].link;
    }
    else {
      list[start].link = second; 
      start = second;
      second = list[second].link;
    } 
  }if (first == -1)
    list[start].link = second;
  else list[start].link = first;
  return list[n].link; 
  // 합병된 리스트의 시작 인덱스를 return
}

listmerge takes two sorted chains, first and second, and returns an integer that points to the start of a new sorted chain that includes the first and second chains.
listmerge 함수 수행 예 start

alg