今天就透過一些有趣的短片來解釋 Insertion Sort 和 Merge Sort 吧 ～

Insertion Sort

Insertion Sort 通常用於小型數據集或部分有序的數據。

其工作方式類似於整理一手扑克牌的過程，不斷將一張牌插入已排序的牌中，直到所有牌都被排序為止。

透過將待排序的數據分為已排序區間和未排序區間，初始時已排序區間只包含一個元素，就是待排序數據的第一個元素，然後遍歷未排序區間的元素，逐個插入到已排序區間中的適當位置，使得已排序區間依然保持有序。

演算法

1. 從未排序區間中取出第一個元素，將其視為已排序區間。
2. 遍歷未排序區間的元素，將每個元素插入到已排序區間的正確位置，以保持已排序區間的有序性。
3. 重複步驟2，直到未排序區間中的所有元素都被插入到已排序區間中，排序完成。

其時間複雜度為，其中是待排序數據的數量。

Insertion Sort 是一種簡單但有效的排序算法，適用於小型數據集或部分有序的情況。

// insertion sort
class InsertionSort {
    fun sort(arr: IntArray) {
        val n = arr.size
        for (i in 1 until n) {
            val key = arr[i]
            var j = i - 1
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j]
                j--
            }
            arr[j + 1] = key
        }
    }
}

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(-8, -8, -87, 12, 0, 34, 64, 90, 12)
    val insertionSort = InsertionSort()
    insertionSort.sort(arr)
    println("Sorted array")
    for (i in arr.indices) {
        print(arr[i].toString() + " ")
    }
}

Merge Sort

Merge Sort 是一種分治法（Divide and Conquer）的排序算法，通常用來對一個數組或列表進行排序。

將待排序的數據分為若干個子問題，分別排序這些子問題，然後將已排序的子問題合併成一個整體有序的結果。

合併排序的過程包括兩個主要步驟：

1. 分割
2. 合併

演算法

1. 分割（Divide）：將待排序的數組分為兩個相等（或大致相等）的子數組，這個過程持續遞歸地進行，直到每個子數組只包含一個元素。
2. 排序（Conquer）：對每個子數組進行排序。通常使用遞歸來實現排序過程，當子數組中只有一個元素時，它被視為已排序。
3. 合併（Merge）：將已排序的子數組合併成一個大的有序數組。合併的過程是比較兩個子數組的元素，選擇最小（或最大）的元素放入新的數組中，然後繼續這個過程，直到所有元素都被合併成一個有序的數組。

Merge Sort 的優點是穩定性和穩定的時間複雜度。無論輸入數據的分佈如何，合併排序的時間複雜度始終為，其中是待排序數據的數量。然而，它需要額外的空間來存儲子數組，因此在內存使用方面較其他排序算法要多一些。

它特別適用於對大型數組或列表進行排序，並且不受數據分佈的影響。

// merge sort algorithm
class MergeSort {
    fun merge(arr: IntArray, l: Int, m: Int, r: Int) {
        // Find sizes of two subarrays to be merged
        val n1 = m - l + 1
        val n2 = r - m

        /* Create temp arrays */
        val L = IntArray(n1)
        val R = IntArray(n2)

        /*Copy data to temp arrays*/
        for (i in 0 until n1) L[i] = arr[l + i]
        for (j in 0 until n2) R[j] = arr[m + 1 + j]

        /* Merge the temp arrays */
        // Initial indexes of first and second subarrays
        var i = 0
        var j = 0

        // Initial index of merged subarry array
        var k = l
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i]
                i++
            } else {
                arr[k] = R[j]
                j++
            }
            k++
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i]
            i++
            k++
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j]
            j++
            k++
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    fun sort(arr: IntArray, l: Int, r: Int) {
        if (l < r) {
            // Find the middle point
            val m = (l + r) / 2

            // Sort first and second halves
            sort(arr, l, m)
            sort(arr, m + 1, r)

            // Merge the sorted halves
            merge(arr, l, m, r)
        }
    }
}

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(-57, 12, -8, 0, 34, 64, 90, 12)
    val mergeSort = MergeSort()
    mergeSort.sort(arr, 0, arr.size - 1)
    println("Sorted array")
    for (i in arr.indices) {
        print(arr[i].toString() + " ")
    }
}

所有 Code 可以在 Github 找到 ～

明天接著介紹 Quick Sort 和 Heap Sort