Merge Sort (合併排序)

Sorting Problem

Input: A sequence of n numbers { $a_0, a_1, ... , a_{n-1}$}

Output: A permutation (reordering) { $a'_0, a'_1, ... , a'_{n-1}$} of the input sequence such that $a'_0 \leq a'_1 \leq ... \leq a'_{n-1}$

Merge Sort 概念

採用 divide-and-conquer approach:

Divide: 把長度為 $n$ 的 array 分成兩半，左半邊 array: { $a_0, a_1, ..., a_{\frac{n}{2}}$ } 右半邊 array: { $a_{\frac{n}{2}+1}, a_{\frac{n}{2}+2}, ... , a_{n-1}$}。

Conquer: 把左半邊 array 及右半邊 array 分別以 Merge Sort 進行 sorting。 (recursive)

Combine: merge 左半邊及右半邊 sorted array。

C++ implementation

	#include <iostream>
	#include <vector>
	#include <limits>
	using namespace std;
	void printArray(vector<int> &vec) {
	for (int i=0; i<vec.size(); i++) {
	cout << vec[i] << " ";
	}
	cout << endl;
	}
	void merge(vector<int> &vec, int front, int mid, int end) {
	// preconditions:
	// Array[front...mid] is sorted
	// Array[mid+1 ... end] is sorted
	// Copy Array[front ... mid] to LeftSubArray
	// Copy Array[mid+1 ... end] to RightSubArray
	vector<int> leftSubArray(vec.begin()+front, vec.begin()+mid+1);
	vector<int> rightSubArray(vec.begin()+mid+1, vec.begin()+end+1);
	int idxLeft = 0, idxRight = 0;
	leftSubArray.insert(leftSubArray.end(), numeric_limits<int>::max());
	rightSubArray.insert(rightSubArray.end(), numeric_limits<int>::max());
	// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
	for (int i = front; i <= end; i++) {
	if (leftSubArray[idxLeft] < rightSubArray[idxRight]) {
	vec[i] = leftSubArray[idxLeft];
	idxLeft++;
	} else {
	vec[i] = rightSubArray[idxRight];
	idxRight++;
	}
	}
	}
	void mergeSort(vector<int> &vec, int front, int end) {
	if (front>=end)
	return;
	int mid = (front + end)/2;
	mergeSort(vec, front, mid);
	mergeSort(vec, mid+1, end);
	merge(vec, front, mid, end);
	}
	int main(int argc, char** argv) {
	int array1[] = {38, 27, 43, 3, 9, 82, 10};
	vector<int> vec1(array1, array1+sizeof(array1)/sizeof(array1[0]));
	cout << "original array:" << endl;
	printArray(vec1);
	mergeSort(vec1, 0, vec1.size()-1);
	cout << "sorted array:" << endl;
	printArray(vec1);
	return 0;
	}

view raw MergeSort.cpp hosted with ❤ by GitHub

範例

藍色數字為執行的順序。

	Step: 1 MergeSort
	front: 0 end: 6
	sub array: 38 27 43 3 9 82 10
	Step: 2 MergeSort
	front: 0 end: 3
	sub array: 38 27 43 3
	Step: 3 MergeSort
	front: 0 end: 1
	sub array: 38 27
	Step: 4 MergeSort
	front: 0 end: 0
	sub array: 38
	Step: 5 MergeSort
	front: 1 end: 1
	sub array: 27
	Step: 6 Merge
	front: 0 end: 1
	sub array: 38 27
	Step: 7 MergeSort
	front: 2 end: 3
	sub array: 43 3
	Step: 8 MergeSort
	front: 2 end: 2
	sub array: 43
	Step: 9 MergeSort
	front: 3 end: 3
	sub array: 3
	Step: 10 Merge
	front: 2 end: 3
	sub array: 43 3
	Step: 11 Merge
	front: 0 end: 3
	sub array: 27 38 3 43
	Step: 12 MergeSort
	front: 4 end: 6
	sub array: 9 82 10
	Step: 13 MergeSort
	front: 4 end: 5
	sub array: 9 82
	Step: 14 MergeSort
	front: 4 end: 4
	sub array: 9
	Step: 15 MergeSort
	front: 5 end: 5
	sub array: 82
	Step: 16 Merge
	front: 4 end: 5
	sub array: 9 82
	Step: 17 MergeSort
	front: 6 end: 6
	sub array: 10
	Step: 18 Merge
	front: 4 end: 6
	sub array: 9 82 10
	Step: 19 Merge
	front: 0 end: 6
	sub array: 3 27 38 43 9 10 82

view raw MergeSort_example_trace.txt hosted with ❤ by GitHub

Performance Analysis

Running time $T(n) = 2 T(\frac{n}{2}) + O(n)$

Worst case performance: $O(n \log n)$

Average case performance: $O(n \log n)$

Best case performance: $O(n \log n)$

Space complexity: $O(n)$

延伸閱讀

[書籍] Introduction to Algorithms, 3rd. edition - Chap 2

[WiKi] 合併排序

[WiKi] Merge sort

系列文章

Insertion Sort (插入排序)

Merge Sort (合併排序)

Heapsort (堆積排序)