演算法 - 合併排序法 (Merge Sort)

簡介

合併排序法 (或稱歸併排序法)，是排序演算法的一種，使用 Divide and Conquer 的演算法來實作。排序時需要額外的空間來處理，過程依照以下步驟進行：

1. 將陣列分割直到只有一個元素。
2. 開始兩兩合併，每次合併同時進行排序，合併出排序過的陣列。
3. 重複2的動作直到全部合併完成。

流程範例如圖所示：

實作又可分為 Top-down 和 Bottom-up，依據原始的步驟會先將陣量分割直到剩一個元素 (Top-down)，然而也可以一開始就直接切割成單一元素開始合併 (Bottom-up)。

分析

• 最佳時間複雜度：O(nlog n)
• 平均時間複雜度：O(nlog n)
• 最差時間複雜度：O(nlog n)
• 空間複雜度：O(n)
• Stable sort：是

虛擬碼

以下以較高階的想法寫出虛擬碼，實作上效能要好必須還要進一步修改：

Top-down

function sort(list)
	if list.length == 1
		return list
	end if
	left = 取出從 list[0] 到 list[list.length / 2 - 1]
	right = 取出從 list[list.length / 2] 到 list[list.length - 1]
	return merge(sort(left), sort(right))
end function

function merge(left, right)
	var result = []
	while left.length > 0 && right.length > 0
		if right[0] < left[0]
			pop right 加到 result
		else
			pop left 加到 result
		end if
	end while
	left 剩下的加到 result
	right 剩下的加到 result
	return result
end function

Bottom-up

function sort(list)
	// count 為每個已排序的子陣列長度，每次合併後每個已排序的片段長度都會加倍，故增量為乘 2
	for count = 1; count < list.length; count *= 2
		var work = []
		// 每次取兩個片段來合併，故增量為兩個片段長度
		for leftStart = 0; leftStart < list.length; leftStart += count * 2
			rightStart = min(leftStart + count, list.length - 1)
			left = 取出從 list[leftStart] 到 list[rightStart - 1]
			right = 取出從 list[rightStart] 到 list[min(rightStart + count - 1, list.length)]
			// merge 同 Top-down
			merge(left, right) 加到 work
		end for
		list = work
	end for
	return list
end function

語法

C#

Top-down 物件導向的寫法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeSort
{
    // Top-down oo style
    class ObjectOriented
    {
        public static void Sort(int[] array)
        {
            Sort(array.ToList()).ToArray().CopyTo(array, 0);
        }

        private static List<int> Sort(List<int> list)
        {
            if (list.Count < 2)
                return list;

            List<int> left = list.GetRange(0, list.Count / 2);
            List<int> right = list.GetRange(list.Count / 2, list.Count - list.Count / 2);
            return Merge(Sort(left), Sort(right));
        }

        private static List<int> Merge(List<int> left, List<int> right)
        {
            List<int> result = new List<int>(left.Count + right.Count);
            while (left.Count > 0 && right.Count > 0)
                result.Add(right.First() < left.First() ? Pop(right) : Pop(left));
            result.AddRange(left);
            result.AddRange(right);
            return result;
        }

        private static int Pop(List<int> list)
        {
            int i = list.First();
            list.RemoveAt(0);
            return i;
        }
    }
}

Top-down 修改版

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeSort
{
    class TopDown
    {
        public static void Sort(int[] array)
        {
            int[] workArray = new int[array.Length];
            Sort(array, workArray, 0, array.Length);
        }

        private static void Sort(int[] array, int[] workArray, int start, int count)
        {
            if (count < 2)
                return;

            Sort(array, workArray, start, count / 2);
            Sort(array, workArray, start + count / 2, count - count / 2);
            Merge(array, workArray, start, count / 2, start + count / 2, count - count / 2);
        }

        private static void Merge(int[] array, int[] workArray, int leftStart, int leftCount, int rightStart, int rightCount)
        {
            int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart;
            while (i < leftBound || j < rightBound)
            {
                if (i < leftBound && j < rightBound)
                {
                    if (array[j] < array[i])
                        workArray[index] = array[j++];
                    else
                        workArray[index] = array[i++];
                }
                else if (i < leftBound)
                    workArray[index] = array[i++];
                else
                    workArray[index] = array[j++];
                ++index;
            }
            for (i = leftStart; i < index; ++i)
                array[i] = workArray[i];
        }
    }
}

Bottom-up

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeSort
{
    class BottomUp
    {
        public static void Sort(int[] array)
        {
            int[] workArray = new int[array.Length];

            for (int count = 1; count < array.Length; count *= 2)
                for (int leftStart = 0; leftStart < array.Length; leftStart += 2 * count)
                {
                    if (count > array.Length - leftStart)
                        break;
                    Merge(array, workArray, leftStart, count, leftStart + count, Math.Min(count, array.Length - leftStart - count));
                }
        }

        private static void Merge(int[] array, int[] workArray, int leftStart, int leftCount, int rightStart, int rightCount)
        {
            int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart;
            while (i < leftBound || j < rightBound)
            {
                if (i < leftBound && j < rightBound)
                {
                    if (array[j] < array[i])
                        workArray[index] = array[j++];
                    else
                        workArray[index] = array[i++];
                }
                else if (i < leftBound)
                    workArray[index] = array[i++];
                else
                    workArray[index] = array[j++];
                ++index;
            }
            for (i = leftStart; i < index; ++i)
                array[i] = workArray[i];
        }
    }
}

Java

Top-down

public class TopDown {
    public static void Sort(int[] array)
    {
        int[] workArray = new int[array.length];
        Sort(array, workArray, 0, array.length);
    }

    private static void Sort(int[] array, int[] workArray, int start, int count)
    {
        if (count < 2)
            return;

        Sort(array, workArray, start, count / 2);
        Sort(array, workArray, start + count / 2, count - count / 2);
        Merge(array, workArray, start, count / 2, start + count / 2, count - count / 2);
    }

    private static void Merge(int[] array, int[] workArray, int leftStart, int leftCount, int rightStart, int rightCount)
    {
        int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart;
        while (i < leftBound || j < rightBound)
        {
            if (i < leftBound && j < rightBound)
            {
                if (array[j] < array[i])
                    workArray[index] = array[j++];
                else
                    workArray[index] = array[i++];
            }
            else if (i < leftBound)
                workArray[index] = array[i++];
            else
                workArray[index] = array[j++];
            ++index;
        }
        for (i = leftStart; i < index; ++i)
            array[i] = workArray[i];
    }
}

Bottom-up

public class BottomUp {
    public static void Sort(int[] array)
    {
        int[] workArray = new int[array.length];

        for (int count = 1; count < array.length; count *= 2)
            for (int leftStart = 0; leftStart < array.length; leftStart += 2 * count)
            {
                if (count > array.length - leftStart)
                    break;
                Merge(array, workArray, leftStart, count, leftStart + count, Math.min(count, array.length - leftStart - count));
            }
    }

    private static void Merge(int[] array, int[] workArray, int leftStart, int leftCount, int rightStart, int rightCount)
    {
        int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart;
        while (i < leftBound || j < rightBound)
        {
            if (i < leftBound && j < rightBound)
            {
                if (array[j] < array[i])
                    workArray[index] = array[j++];
                else
                    workArray[index] = array[i++];
            }
            else if (i < leftBound)
                workArray[index] = array[i++];
            else
                workArray[index] = array[j++];
            ++index;
        }
        for (i = leftStart; i < index; ++i)
            array[i] = workArray[i];
    }
}

C++

Top-down

TopDown.h

#ifndef TOPDOWN_H
#define TOPDOWN_H


class TopDown
{
    public:
        static void Sort(int* array, int length);
    protected:
    private:
        static void Sort(int* array, int* workArray, int length, int start, int count);
        static void Merge(int* array, int* workArray, int length, int leftStart, int leftCount, int rightStart, int rightCount);
};

#endif // TOPDOWN_H

TopDown.cpp

#include "TopDown.h"

void TopDown::Sort(int* array, int length)
{
    int* workArray = new int[length];
    Sort(array, workArray, length, 0, length);
}

void TopDown::Sort(int* array, int* workArray, int length, int start, int count)
{
    if (count < 2)
        return;

    TopDown::Sort(array, workArray, length, start, count / 2);
    TopDown::Sort(array, workArray, length, start + count / 2, count - count / 2);
    TopDown::Merge(array, workArray, length, start, count / 2, start + count / 2, count - count / 2);
}

void TopDown::Merge(int* array, int* workArray, int length, int leftStart, int leftCount, int rightStart, int rightCount)
{
    int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart;
    while (i < leftBound || j < rightBound)
    {
        if (i < leftBound && j < rightBound)
        {
            if (array[j] < array[i])
                workArray[index] = array[j++];
            else
                workArray[index] = array[i++];
        }
        else if (i < leftBound)
            workArray[index] = array[i++];
        else
            workArray[index] = array[j++];
        ++index;
    }
    for (i = leftStart; i < index; ++i)
        array[i] = workArray[i];
}

Bottom-up

Bottom.h

#ifndef BOTTOMUP_H
#define BOTTOMUP_H


class BottomUp
{
    public:
        static void Sort(int* array, int length);
    protected:
    private:
        static void Merge(int* array, int* workArray, int length, int leftStart, int leftCount, int rightStart, int rightCount);
};

#endif // BOTTOMUP_H

BottomUp.cpp

#include "BottomUp.h"
#include <algorithm>
using namespace std;

void BottomUp::Sort(int* array, int length)
{
    int* workArray = new int[length];

    for (int count = 1; count < length; count *= 2)
        for (int leftStart = 0; leftStart < length; leftStart += 2 * count)
        {
            if (count > length - leftStart)
                break;
            Merge(array, workArray, length, leftStart, count, leftStart + count, min(count, length - leftStart - count));
        }
}

void BottomUp::Merge(int* array, int* workArray, int length, int leftStart, int leftCount, int rightStart, int rightCount)
{
    int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart;
    while (i < leftBound || j < rightBound)
    {
        if (i < leftBound && j < rightBound)
        {
            if (array[j] < array[i])
                workArray[index] = array[j++];
            else
                workArray[index] = array[i++];
        }
        else if (i < leftBound)
            workArray[index] = array[i++];
        else
            workArray[index] = array[j++];
        ++index;
    }
    for (i = leftStart; i < index; ++i)
        array[i] = workArray[i];
}

隨機產生 100000 筆資料實測

C#
TopDown: 50ms
ButtonUp: 40ms

Java
TopDown: 30ms
ButtonUp: 40ms

C++
TopDown: 50ms
BottomUp: 40ms

延伸閱讀

排序演算法 (Sorting)
分治法 (Divide and conquer)