归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
白话说：所谓归并排序，望文生义，就是把两个东西合并在一起了，那么是什么东西合并在一起了呢？是两个已经排好序的数组进行合并到一个数组中，这两个排好序的数组分别有一个指针指向第0个元素，谁小谁放进大数组中。
大致排序过程是这样的：
图摘自–https://www.cnblogs.com/qingmingsang/articles/5283870.html
先把数组中的元素两两比较，创建一个辅助数组，将排好序的数字放进辅助数组中，然后再把辅助数组中的数放回原数组，然后两个合并好的数组再合并，再创建一个辅助数组，再把两个数组中排好序的数字放进辅助数组中，再把辅助数组放回原数组中，直到所有的数组全部排好序。
看一下代码：
package com.bean.com.bean.sortAlg;
import java.util.Arrays;
public class MargeSort {
public static void MergeSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
MergeSort(arr, 0, arr.length - 1);
}
public static void MergeSort(int[] arr, int left, int right) {
if(left == right) {
return;
}
int mid = left + ((right - left)>>1);//等于(left+right)/2，位运算比较快
MergeSort(arr, left, mid);//把左边的元素全拆开
MergeSort(arr, mid+1, right);//把右边的元素全拆开
MergeSort(arr, left, mid, right);//left~right之间排序
}
public static void MergeSort(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];//辅助数组，暂存排好序的元素
int index = 0;
int p1 = left;//左指针
int p2 = mid + 1;//右指针
while(p1 <= mid && p2 <= right) {//只要左右指针没超出范围，就排序
help[index++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
//谁小谁先入help数组
}
while(p2 <= right) {//p1排完了，p2还有没排完的元素，则依次入数组
help[index++] = arr[p2++];
}
while(p1 <= mid) {//p2排完了,p1继续依次扔进help数组
help[index++] = arr[p1++];
}
for(int i = 0; i < help.length; i++) {
arr[left + i] = help[i];//把排好序的元素放回原数组中！
}
}
//打印数组
public static void printArray(int[] arr) {
if(arr == null) {
return;
}
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
//形成随机数组
public static int[] generateRandomArray(int maxSize, int maxNum) {
if(maxSize <= 0) {
return null;
}
int[] ranArray = new int[(int) (Math.random() * (maxSize + 1) )];
for(int i = 0; i < ranArray.length; i++) {
ranArray[i] = (int) (Math.random() * (maxNum + 1)) - (int) (Math.random() * maxNum);
}
return ranArray;
}
//判断两个数组是否相等
public static boolean isEquals(int[] arr1, int[] arr2) {
if(arr1.length != arr2.length) {
return false;
}
if(arr1 == null && arr2 != null || arr1 != null && arr2 == null) {
return false;
}
if(arr1 == null && arr2 == null) {
return true;
}
for(int i = 0; i < arr1.length; i++) {
if(arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
//完全正确的排序方法
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
//复制数组
public static int[] copyArray(int[] arr) {
int[] newArr = new int[arr.length];
for(int i = 0; i < arr.length; i++) {
newArr[i] = arr[i];
}
return newArr;
}
public static void main(String[] args) {
int testTimes = 100000;
int maxNum = 100;
int maxSize = 2000;
boolean flag = true;
for(int i = 0; i < testTimes; i++) {
int[] arr1 = generateRandomArray(maxSize, maxNum);
int[] arr2 = copyArray(arr1);
comparator(arr1);
MergeSort(arr2);
if(!isEquals(arr1, arr2)){
flag = false;
break;
}
}
System.out.println(flag ? "Nice! Nothing is wrong~" : "Ooops! Your method is wrong..");
int[] arr1 = generateRandomArray(maxSize, maxNum);
System.out.print("before:");printArray(arr1);
long beforetime = System.currentTimeMillis();
MergeSort(arr1);
long aftertime = System.currentTimeMillis();
System.out.println("execute time is:"+(aftertime - beforetime)+"ms");
System.out.print("after");printArray(arr1);
}
}
其实就是把一个数组进行拆块，每一小块都排序，然后再把两个排好序的小块整合，再进行排序，直到所有小块都排好序，整体排序结束。
时间复杂度
假如有N个元素，那么每次二分，它的时间复杂度是logN，但是每次二分完了还需要进行比较，比较的次数跟有多少个元素N有关，所以整体时间复杂度是O(n*logn)，额外空间复杂度说的就是那个辅助数组，它每次创建完又被销毁了，所以额外的空间复杂度是O(n)，但是根据内部缓存法，可以使额外空间复杂度变成O（1），比较难，所以本篇博客不作记载，如有需要请自行百度。