CODEWITHSUNDEEP
algorithmgomergesort
eAbi
eAbi

Reputation: 3450

What is wrong with the following merge sort algorithm?

As the question states, I'm having trouble finding where is the issue within the following algorithm. It is the aux function for mergesort, i.e. the one used for combining sorted arrays.

func Merge(toSort *[]int, p, q, r int) {
    arr := *toSort
    L := arr[p:q]
    R := arr[q:r+1]
    fmt.Println(L)
    fmt.Println(R)
    i := 0
    j := 0

    for index := p; index <= r; index++ {
        if i >= len(L) {
            arr[index] = R[j]
            j += 1
            continue
        } else if j >= len(R) {
            arr[index] = L[i]
            i += 1
            continue
        }

        if L[i] > R[j] {
            fmt.Println("right smaller")
            arr[index] = R[j]
            j += 1
            continue
        }
        if L[i] <= R[j] {
            fmt.Println("left smaller")
            arr[index] = L[i]
            i += 1
            continue
        }

    }

}

For arr := []int{1,7,14,15,44,65,79,2,3,6,55,70} it gives as output [1 2 2 2 2 2 2 2 3 6 55 70].

Golang Play link

The JavaScript equivalent for this function works as expected, but I don't know why it isn't working in Go

Thank you

Upvotes: 1

Views: 133

Answers (3)

Paul Hankin
Paul Hankin

Reputation: 58221

You don't need all the indexes: slices are already views into an array. Here's a complete example using purely slice manipulation:

package main

import "fmt"

// Merge takes two sorted, increasing slices of ints and
// returns a slice combining them into a single sorted, increasing
// slice.
func Merge(a, b []int) []int {
    res := make([]int, 0, len(a)+len(b))
    for len(a) > 0 || len(b) > 0 {
        if len(b) == 0 || len(a) > 0 && a[0] <= b[0] {
            res = append(res, a[0])
            a = a[1:]
        } else {
            res = append(res, b[0])
            b = b[1:]
        }
    }
    return res
}

func main() {
    a := []int{1, 2, 5, 6, 3, 4, 7, 9}
    fmt.Println(Merge(a[:4], a[4:]))
}

Upvotes: 1

Evan
Evan

Reputation: 6545

Golang slices are passed by reference. So you don't need to pass a pointer into the function in the first place, but you do need to take explicit copies of L and R or else merge into a different slice entirely. You are currently writing into the same underlying memory from which you are getting your values.

Upvotes: 2

Volker
Volker

Reputation: 42413

Code like L := arr[p:q] does not create a copy. I suppose you are overwriting your L and R parts during the assignments to arr. Have a look at http://blog.golang.org/slices to understand how slices work. (E.g. you'll basically never write stuff like toSort *[]int as []int is almost kinda pointer)

This seems to work: http://play.golang.org/p/vPo2ZKXtI9

Upvotes: 1

Related Questions