MergeSort算法

MergeSort 算法

1.问题

对一个数组进行排序，使其有序

2.解析

利用归并算法，将数组不断拆分成一个数字，最后不断归并、返回，形成一个有序数组。

3.设计

MergeSort算法

function void merge(int[] array, int left, int mid, int right)
	int[] temp ←new int[right – left + 1];
	int s1 ←left, s2 ←mid + 1, index ←0;
	while s1 <= mid and s2 <= right do:
		if array[s1] <= array[s2] do:
			temp[index] ← array[s1];
			index ← index + 1;
				s2 ← s2 + 1;
			else do:
				temp[index] ← array[s2];
				index ← index + 1;
				s2 ←  s2 + 1;
		while s1 <= mid do:
		temp[index] ← array[s1];
		index ← index + 1;
			s2 ← s2 + 1;
		while s2 <= right do:
			temp[index] ← array[s2];
			index ← index + 1;
			s2 ←  s2 + 1;

		for I = 0 to temp.length do:
			array[I + left] = temp[i];

	function void mergesort(int[] array, int start, int end)
		if start >= end return;
		int mid = (start + end) >>> 1;
		mergesort(array, start, mid);
		mergesort(array, mid + 1, end);
		merge(array, mid + 1, end);

4.分析

O(n) =log2n

5.源码

https://github.com/JessySnow/Algorithm/blob/master/src/T4/MergeSort.java

MergeSort算法

原文：https://www.cnblogs.com/jessysnow/p/14603845.html