归并排序

发表于   |   分类于

简介

要将一个数组排序，可以先（递归地）将它分为两半分别排序，然后将结果归并起来。

优点： 将任意长度为 N 的数组排序所需时间和 NlogN 成正比；
缺点：所需的额外空间和 N 成正比。

Basic Plan

  • Divide array into two halves.
  • Recursively sort each half.
  • Merge two halves.

代码

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
public class Merge {
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        assert isSorted(a, lo, mid); // precondition: a[lo..mid] sorted
        assert isSorted(a, mid + 1, hi); // precondition: a[mid+1..hi] sorted

        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        int i = lo, j = mid + 1;
        for (int k = lo; k < hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }

        assert isSorted(a, lo, hi);
    }

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }
}

Mergesort: practical improvements

Use insertion sort for small subarrays

  • Mergesort has too much overhead for tiny subarrays.
  • Cutoff to insertion sort for ≈ 7 items.
1
2
3
4
5
6
7
8
9
10
11
12
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    // Use insertion sort for small subarrays
    if (hi <= lo + CUTOFF - 1) {
        Insertion.sort(a, lo, hi);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort (a, aux, lo, mid);
    sort (a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

Stop of already sorted.

  • Is biggest item in first half <= smallest item in second half?
  • Helps for partially-ordered arrays.
1
2
3
4
5
6
7
8
9
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort (a, aux, lo, mid);
    sort (a, aux, mid+1, hi);
    if (!less(a[mid+1], a[mid])) return; // if already sorted then return
    merge(a, aux, lo, mid, hi);
}