手撕二路归并排序-Java代码

手撕二路归并排序

复杂度和稳定性

时间复杂度：

1. 最好：O(nlog2n)
2. 最坏：O(nlog2n)
3. 平均：O(nlog2n)

空间复杂度：O(n)

稳定性：稳定

Java代码

public class MergeSort {

	public int[] mergeSort(int[] array, int left, int right) {
		if(left == right) {  // 当数组只有一个元素，直接返回单元素数组
			return new int[] { array[left] };
		}
		
		int mid = ( left + right ) / 2;  // 找到数组中点
		int[] leftArray = mergeSort(array, left, mid);        // 左侧数组：递归归并排序左侧数组
		int[] rightArray = mergeSort(array, mid + 1, right);  // 右侧数组：递归归并排序右侧数组
		int[] mergeArray = new int[leftArray.length + rightArray.length];
		
		int leftCursor = 0, rightCursor = 0, mergeCursor = 0;  // 定义左侧数组游标，右侧数组游标，合并数组游标
		
		while (leftCursor < leftArray.length && rightCursor < rightArray.length) {  // 当有一个游标到头就停止
			if (leftArray[leftCursor] < rightArray[rightCursor]) {
				mergeArray[mergeCursor] = leftArray[leftCursor];
				leftCursor++;
			} else {
				mergeArray[mergeCursor] = rightArray[rightCursor];
				rightCursor++;
			}
			mergeCursor++;
		}
		while (leftCursor < leftArray.length) {  // 将左侧游标走完
			mergeArray[mergeCursor] = leftArray[leftCursor];
			leftCursor++;
			mergeCursor++;
		}
		while (rightCursor < rightArray.length) {  // 将右侧游标走完
			mergeArray[mergeCursor] = rightArray[rightCursor];
			rightCursor++;
			mergeCursor++;
		}
		return mergeArray;  // 返回合并数组
	}
	
	public static void main(String[] args) {
		MergeSort ms = new MergeSort();
		int[] array = {54,8,9,84,71,6,31,20,15,80,94,2,17,22,28,98,21,30};
		int[] resArray = ms.mergeSort(array, 0, array.length - 1);
		
		for (int i : resArray) {
			System.out.print(i + "  ");
		}
	}
}