这篇文章写自英文，阅读原文章.
由于本文暂未被翻译成中文，请使用下面工具选项进行翻译

Merge Sort

Merge Sort

Pseudocode

Algorithm 9: Merge Sort

Analysis

  • Because merge sort divides the list first, an even split is guaranteed
  • After the recursion, a linear amount of work is done to merge the two lists
  • Basic idea:
    • Keep two index pointers to each sublist
    • Copy the minimal element, advance the pointer
    • Until one list is empty, then just copy the rest of the other
  • Requires use of $O(n)-$sized temporary array
  • Recurrence: $$C(n)=2C\frac{n}{2}+n$$
  • By the Master Theorem, $O(n log n)$
  • In fact, a guarantee (best, worst, average are the same)

Code Samples

Code Sample 18: Java Merge Sort for integers
1
2
3
4
5
6
7
8
9
public static void mergeSort (int a [] , int low , int high )
{
  if ( low < high ) {
    int middle = ( low + high ) / 2;
    mergesort ( low , middle ) ;
    mergesort ( middle + 1 , high ) ;
    merge ( low , middle , high ) ;
  }
}
Code Sample 19: Java Merge for integers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private static int MERGE_HELPER [];
...

private static void merge (int a [] , int low , int middle , int high )
{
  // Copy both parts into the helper array
  for (int i = low ; i <= high ; i ++) {
    MERGE_HELPER [ i ] = a [ i ];
  }
  int i = low ;
  int j = middle + 1;
  int k = low ;
  // Copy the smallest values from the left or the right side back to the original array
  while ( i <= middle && j <= high ) {
    if ( MERGE_HELPER [ i ] <= MERGE_HELPER [ j ]) {
      a [ k ] = MERGE_HELPER [ i ];
      i ++;
    } else {
      a [ k ] = MERGE_HELPER [ j ];
      j ++;
    }
    k ++;
  }
  // Copy the rest of the left side of the array into the targetarray
  while ( i <= middle ) {
    a [ k ] = MERGE_HELPER [ i ];
    k ++;
    i ++;
  }
  // Copy the rest of the right side of the array into the target array
  while ( j <= high ) {
    a [ k ] = MERGE_HELPER [ j ];
    k ++;
    j ++;
  }
}
Code Sample 20: C Merge Sort for integers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void mergeSort (int * array , int left , int right )
{
  int mid = ( left + right ) /2;
  /* We have to sort only when left < right because when left = right it is anyhow sorted */
  if( left < right )
  {
  /* Sort the left part */
  mergeSort ( array , left , mid ) ;
  /* Sort the right part */
  mergeSort ( array , mid +, right ) ;
  /* Merge the two sorted parts */
  merge ( array , left , mid , right ) ;
  }
}