Mergesort无法正确计算1的左右大小

Question

I'm not sure why left size and right size of the merge operations don't seem to work for for left = 0, mid = 0 and right = 1. Because of these calcs the slicing of the left and right array don't make any sense. The mergesort algo assumes that one of these arrays has to have values for it to even be in the merge portion of the code. This is leading to index errors :(

https://play.golang.org/p/Fmj4xNQTL8W

package main

import (
    "fmt"
)

func merge(arr []int, l, mid, r int) {
    leftSize := mid - l + 1
    rightSize := r - mid

    left := arr[l:mid]
    right := arr[mid+1 : r]

    fmt.Printf("l:%v, m:%v, r:%v
", l, mid, r)
    fmt.Printf("left: size:%v arr:%v, right: size:%v arr:%v
", leftSize, l, rightSize, r)

    /*
        i = left array pointer
        j = right array pointer
        k = original array pointer
    */
    i, j, k := 0, 0, l

    for i < leftSize && j < rightSize {
        if left[i] <= right[j] {
            arr[k] = left[i]
            i++
            k++
        } else {
            arr[k] = right[j]
            j++
            k++
        }
    }

    for i < leftSize {
        arr[k] = left[i]
        i++
        k++
    }
    for j < rightSize {
        arr[k] = right[j]
        j++
        k++
    }
}

func mergeSort(arr []int, left, right int) {
    if left >= right {
        return
    }

    // mid done this way to avoid overflows
    mid := left + (right-left)/2

    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)
    merge(arr, left, mid, right)
}

func main() {
    tc := []int{99, 212, 23, 3, 1, 10}
    mergeSort(tc, 0, len(tc)-1)
    fmt.Printf("%v", tc)
}

Answer 1

There is a few things I would like to suggest:

1. Array range. Dijkstra once argued about how array range (or in Go, slice range), should be like: That for a notation of l[i:j], you would like it have all these properties:

   • It should start at i.
   • It should be trivial to calculate the length: len(l[i:j]) == j-i is always true
   • It should be elegant to express an empty range, so i<=j is always true

Therefore, l[i:j] is set as a half-open range: [i,j), lower-bound included and upper-bound excluded. This also the way Go slicing works (as well as Python and many other languages).

The point is, it is better to keep this convention in your code: when doing range, include lower-bound and exclude upper-bound.

1. Slicing is built in Go. You can utilize it and it is cheap. You don't need to calculate all these l, r, mid in such a verbose and error-prone way, you just need to slice the slice.

For example:

func mergeSort(arr []int) {
    size := len(arr)

    if size <= 1 {
        return
    }
    mid := size / 2
    mergeSort(arr[:mid])
    mergeSort(arr[mid:])
    merge(arr, arr[:mid], arr[mid:])
}

The code is much clearer and more robust.

1. A slicing does not do a deep-copy, which means, left := arr[l:mid] only creates a pointer to the elements of arr. It is why I said slicing is cheap in Go.

However, without a deep copy, when you merge the slices, the data is overwritten and therefore corrupted. You need to merge into a new slice and then copy it back to the orignal slice. This is why naive mergesort is considered to have a O(n) extra memory use.

func merge(arr, left, right []int) {
    res := make([]int, len(arr))
    leftSize, rightSize := len(left), len(right)

    var i,j,k int
    for i = range res {
        if j >= leftSize || k >= rightSize {
            break
        }

        if left[j] <= right[k] {
            res[i] = left[j]
            j++
        } else {
            res[i] = right[k]
            k++
        }
    }

    // Only one of these two copies run, so no need to increase i
    copy(res[i:], left[j:])
    copy(res[i:], right[k:])

    copy(arr, res)
}

Playground: https://play.golang.org/p/LlJj-JycfYE