Блог

Я просматриваю книгу Learning Algorithms Джорджа Хайнемана. Все приведенные в книге примеры написаны на Python, и до сих пор у меня не возникало проблем с их переводом на Go, пока я не столкнулся с алгоритмом сортировки слиянием.

Вот код, который я придумал (см. На Go Playground:

 package main

import "fmt"

func mergeSort(a []int) {
    aux := make([]int, len(a))

    merge := func(low, mid, high int) {
        copy(aux[low:high 1], a[low:high 1])

        left, right := low, mid 1

        for i := range aux[low : high 1] {
            switch {
            case left > mid:
                a[i] = aux[right]
                right  
            case right > high:
                a[i] = aux[left]
                left  
            case aux[right] < aux[left]:
                a[i] = aux[right]
                right  
            default:
                a[i] = aux[left]
                left  
            }
        }
    }

    var rsort func(int, int)
    rsort = func(low, high int) {
        if high <= low {
            return
        }
        mid := (low   high) / 2

        rsort(low, mid)
        rsort(mid 1, high)
        merge(low, mid, high)
    }

    rsort(0, len(a)-1)
}

func main() {
    array := []int{4, 76, 3, 223, 90, 69, 98, 75, 62}
    fmt.Println(array)

    mergeSort(array)
    fmt.Println(array)
}
 

Я немного не понимаю, почему он не работает, и попытался настроить некоторые свойства.

Для справки, вот исходный код Python: https://github.com/heineman/LearningAlgorithms/blob/main/ch05/merge.py#L5