Merge Sort - 归并排序

核心：将两个有序对数组归并成一个更大的有序数组。通常做法为递归排序，并将两个不同的有序数组归并到第三个数组中。

先来看看动图，归并排序是一种典型的分治应用。

Merge Sort

Python

  1. #!/usr/bin/env python
  4. class Sort:
  5.     def mergeSort(self, alist):
  6.         if len(alist) <= 1:
  7.             return alist
  9.         mid = len(alist) / 2
  10.         left = self.mergeSort(alist[:mid])
  11.         print("left = " + str(left))
  12.         right = self.mergeSort(alist[mid:])
  13.         print("right = " + str(right))
  14.         return self.mergeSortedArray(left, right)
  16.     #@param A and B: sorted integer array A and B.
  17.     #@return: A new sorted integer array
  18.     def mergeSortedArray(self, A, B):
  19.         sortedArray = []
  20.         l = 0
  21.         r = 0
  22.         while l < len(A) and r < len(B):
  23.             if A[l] < B[r]:
  24.                 sortedArray.append(A[l])
  25.                 l += 1
  26.             else:
  27.                 sortedArray.append(B[r])
  28.                 r += 1
  29.         sortedArray += A[l:]
  30.         sortedArray += B[r:]
  32.         return sortedArray
  34. unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
  35. merge_sort = Sort()
  36. print(merge_sort.mergeSort(unsortedArray))

原地归并

Java

  1. public class MergeSort {
  2.     public static void main(String[] args) {
  3.         int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
  4.         mergeSort(unsortedArray);
  5.         System.out.println("After sort: ");
  6.         for (int item : unsortedArray) {
  7.             System.out.print(item + " ");
  8.         }
  9.     }
  11.     private static void merge(int[] array, int low, int mid, int high) {
  12.         int[] helper = new int[array.length];
  13.         // copy array to helper
  14.         for (int k = low; k <= high; k++) {
  15.             helper[k] = array[k];
  16.         }
  17.         // merge array[low...mid] and array[mid + 1...high]
  18.         int i = low, j = mid + 1;
  19.         for (int k = low; k <= high; k++) {
  20.             // k means current location
  21.             if (i > mid) {
  22.             // no item in left part
  23.                 array[k] = helper[j];
  24.                 j++;
  25.             } else if (j > high) {
  26.             // no item in right part
  27.                 array[k] = helper[i];
  28.                 i++;
  29.             } else if (helper[i] > helper[j]) {
  30.             // get smaller item in the right side
  31.                 array[k] = helper[j];
  32.                 j++;
  33.             } else {
  34.             // get smaller item in the left side
  35.                 array[k] = helper[i];
  36.                 i++;
  37.             }
  38.         }
  39.     }
  41.     public static void sort(int[] array, int low, int high) {
  42.         if (high <= low) return;
  43.         int mid = low + (high - low) / 2;
  44.         sort(array, low, mid);
  45.         sort(array, mid + 1, high);
  46.         merge(array, low, mid, high);
  47.         for (int item : array) {
  48.             System.out.print(item + " ");
  49.         }
  50.         System.out.println();
  51.     }
  53.     public static void mergeSort(int[] array) {
  54.         sort(array, 0, array.length - 1);
  55.     }
  56. }

时间复杂度为 O(N \log N), 使用了等长的辅助数组，空间复杂度为 O(N)。

Reference

  • Mergesort - Robert Sedgewick 的大作，非常清晰。