Merge Sort 归并排序

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm.

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

归并排序也是基于分治法的排序算法, 将每个区间分成两个子区间, 将每个子区间排序后进行合并.

归并排序有递归和迭代两种做法.

时间复杂度: $O(nlogn)$

空间复杂度: $O(n)$

1. 递归

空间上需要额外的递归调用栈

func sortArray(nums []int) []int {
    return mergeSort(nums)   
}

func mergeSort(nums []int) []int{
    // one element
    if len(nums) <= 1 {
        return nums
    }

    // split 
    mid := len(nums) >> 1
    left := nums[:mid]
    right := nums[mid:]
    
    return merge(mergeSort(left), mergeSort(right))
}

func merge(left, right []int) []int {
    res := make([]int, 0, max(len(left), len(right)))

    for len(left) != 0 && len(right) != 0 {
        if left[0] < right[0] {
            res = append(res, left[0])
            left = left[1:]
        } else {
            res = append(res, right[0])
            right = right[1:]
        }
    }

    if len(left) == 0 {
        res = append(res, right...)
    } else {
        res = append(res, left...)
    }

    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

2. 迭代

构造一个长度相同的辅助数组, 以长度wid(初始为1)的区间开始, 将原数组分为多个长度尽量相同的区间(最后一个区间可能短一些):

1. 将相邻区间排序后合并

2. 将辅助数组作为当前操作数组, 即和原数组交换

3. 区间长度扩大为原来的两倍, 继续执行步骤1) 直到区间长度和数组长度相同

4. 排序完毕, 原数组已排序

func sortArray(nums []int) []int {
    return mergeSort(nums)
}

func mergeSort(nums []int) []int{
    length := len(nums)
    tmp := make([]int, length)

    // 区间长度wid
    // 每次倍增 
    for wid := 1; wid < length; wid += wid {
        // 每个区间的首个元素索引
        for start := 0; start < length; start += wid*2 {
            mid := min(start+wid, length) // 当前区间的右边界
            end := min(start+wid*2, length) // 相邻区间的右边界
            i := start // 当前区间索引
            j := mid   // 相邻区间索引
            k := start // 辅助数组索引 
            
            // 合并区间
            for i < mid || j < end {
                if j == end || (i < mid && nums[i] < nums[j]) {
                    tmp[k] = nums[i]
                    k++
                    i++
                } else {
                    tmp[k] = nums[j]
                    k++
                    j++
                }
            }
        }

        // 切换当前操作数组
        tmp, nums = nums, tmp
    }

    return nums
}

func min(a, b int) int {
    if a < b {
        return  a
    }
    return b
}

3. Leetcode

912. 排序数组

Reference

1. 912. 排序数组
2. https://en.wikipedia.org/wiki/Merge_sort
3. https://www.runoob.com/w3cnote/merge-sort.html
4. https://www.runoob.com/w3cnote/ten-sorting-algorithm.html