一）定义
归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。
二）归并排序实现——两路归并（java）
package com.fox;
import java.util.Random;
/**
* @author huangfox
* @serial 合并排序
*/
public class MergeSort {
public static void sort(int[] seq) {
mergeSort(seq, 0, seq.length - 1);
}
/**
* 分治，采用
*
* @param seq
* @param s
* @param e
*/
public static void mergeSort(int[] seq, int s, int e) {
if (s < e) {
int m = (s + e) / 2;
mergeSort(seq, s, m);
mergeSort(seq, m + 1, e);
merge(seq, s, m, e);
}
}
private static void merge(int[] seq, int s, int m, int e) {
int n1 = m - s + 1;
int n2 = e - m;
int[] ls = new int[n1];
for (int i = 0; i < ls.length; i++) {
ls[i] = seq[s + i];
}
int[] rs = new int[n2];
for (int i = 0; i < rs.length; i++) {
rs[i] = seq[m + i + 1];
}
int index = s;
int i1 = 0;
int i2 = 0;
while (i1 < n1 && i2 < n2) {
if (ls[i1] < rs[i2]) {
seq[index++] = ls[i1++];
} else {
seq[index++] = rs[i2++];
}
}
while (i1 < n1) {
seq[index++] = ls[i1++];
}
while (i2 < n2) {
seq[index++] = rs[i2++];
}
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a = new int[100000];
Random random = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = random.nextInt(100000);
}
// a = new int[] { 6, 7, 51, 2, 52, 8 };
long bt = System.currentTimeMillis();
MergeSort.sort(a);
System.out.println(System.currentTimeMillis() - bt);
for (int a_ : a)
System.out.println(a_);
}
}
归并排序——需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。