归并排序 mergeSort

基本概念

• 将一个数组不断的二分，直到不能分为止
• 然后将不断对比合并
• 归并排序适用于链表，不需要额外的储存空间。但是对于数组，需要额外的储存空间
  

归并排序的实现

/*
Merge Sort:
1. Time complexity:
   worst case: nlogn
   best case:  nlogn
   averge:     nlogn

2. This is a stable sorting 
3.  merge sort is best for Linked List, since linked list is easy to break and 
   re-linked, there is no additional space required. In addition, merge sort does
   not require insert and traverse methods.
      For an array, merge sort requires additional space (the temp array to store
   sorted value)
*/

package sorting;
import java.util.*;
public class MergeSort {  
	
	public void mergeSort(int [] array) {
		int [] temp = new int[array.length];
		sort(0, array.length-1, array, temp);
	}
	
	private void sort(int left, int right, int [] data, int [] temp) {
	    //只有一个元素时，返回
		if (left >= right) {
			return;
		}
	    
	    //不断的二分，进入递归
		sort(left, (left + right)/2, data, temp);
		sort((left + right)/2 + 1, right, data, temp);
		merge(left, right, data, temp);
	}
	
	private void merge(int start, int end, int [] data, int [] temp) {
		int mid = (start + end) / 2;
		int leftStart = start;
		int rightStart = mid + 1;
		int tempIndex = leftStart;
		
		//合并数组的前半部分和后半部分
		while (leftStart <= mid && rightStart <= end) {
			if (data[leftStart] <= data[rightStart]) {
				temp[tempIndex] = data [leftStart];
				tempIndex++;
				leftStart++;
			}
			else {
				temp[tempIndex] = data [rightStart];
				tempIndex++;
				rightStart++;
			}
		}
		
		//以下两个while loop是为了防止某一部分没有遍历完
		while (leftStart <= mid) {
			temp[tempIndex] = data [leftStart];
			tempIndex++;
			leftStart++;
		}
		
		while (rightStart <= end) {
			temp[tempIndex] = data [rightStart];
			tempIndex++;
			rightStart++;
		}
		//将temp赋值给input array
		for (int i = start; i <= end; i++) {
			data[i] = temp[i];
		}	
	}
}

时间复杂度 和 空间复杂度

• 时间复杂度：最坏情况，最好情况， 平均情况： O(nlogn)
• 空间复杂度： 在归并时需要使用一个额外的数组储存元素，所以是 O(n)

稳定性

• 归并排序是稳定排序

while (leftStart <= mid && rightStart <= end) {
            //只有当这里是 data[leftStart] <= data[rightStart]，有等于号才是稳定排序
            //这样靠左的数才能被放到左边
			if (data[leftStart] <= data[rightStart]) {
				temp[tempIndex] = data [leftStart];
				tempIndex++;
				leftStart++;
			}
			else {
				temp[tempIndex] = data [rightStart];
				tempIndex++;
				rightStart++;
			}
		}