基本思想
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型的应用。它的基本操作是：将已有的子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
image
算法实现
package cn.caojiantao.tutorials.sort;
/**
* @author caojiantao
*/
public class Merge implements ISort {
@Override
public void sort(int[] data) {
sort(data, 0, data.length - 1);
}
private void sort(int[] data, int start, int end) {
if (start < end) {
int m = (start + end) / 2, i = start, j = m + 1, cursor = 0;
// 分
sort(data, start, m);
sort(data, m + 1, end);
// 而治之
int[] tmp = new int[end - start + 1];
while (i <= m && j <= end) tmp[cursor++] = (data[i] <= data[j]) ? data[i++] : data[j++];
while (i <= m) tmp[cursor++] = data[i++];
while (j <= end) tmp[cursor++] = data[j++];
System.arraycopy(tmp, 0, data, start, tmp.length);
}
}
}
复杂度
- 时间复杂度 O(nlog2n)
- 空间复杂度 O(n)
稳定性
稳定
