4
\$\begingroup\$

This is a problem from Robert Sedgwick's Algorithms book:

Write a version of bottom-up mergesort that takes advantage of order in the array by proceeding as follows each time it needs to find two arrays to merge: find a sorted subarray (by incrementing a pointer until finding an entry that is smaller than its predecessor in the array), then find the next, then merge them.

The code needs to be reviewed for:

  • Correct use of Go
  • Any improvements to the code

// NaturalMergeSort.go
package main

import (
    "fmt"
)

type sorting struct {
    arr []int
    aux []int
}

func newSorting(arr []int) *sorting {
    s := new(sorting)
    s.arr = arr
    s.aux = make([]int, len(s.arr))
    return s
}

func (s *sorting) naturalSort() {

    if len(s.arr) <= 1 {
        return
    }

    start := 0
    stop1 := s.getNextStop(start)
    var stop2 int
    for stop1 < len(s.arr)-1 {
        stop2 = s.getNextStop(stop1 + 1)

        // Now merge arrays
        //fmt.Println(start, stop1, stop2)
        s.merge(start, stop1, stop2)
        stop1 = stop2
    }
}

func (s *sorting) merge(start int, stop1 int, stop2 int) {

    // copy first part into aux
    for k := start; k <= stop1; k++ {
        s.aux[k] = s.arr[k]
    }
    i := start
    j := stop1 + 1
    for k := start; k <= stop2; k++ {
        if i > stop1 {
            // copying is done
            break
        } else if j > stop2 {
            s.arr[k] = s.aux[i]
            i++
        } else if s.aux[i] > s.arr[j] {
            s.arr[k] = s.arr[j]
            j++
        } else {
            s.arr[k] = s.aux[i]
            i++
        }
    }
}

func (s *sorting) getNextStop(i int) int {

    for i < len(s.arr)-1 && s.arr[i] < s.arr[i+1] {
        i = i + 1
    }
    return i
}

func main() {
    s := newSorting([]int{5, 3, 4, 10, 1, 6, 8, 2})

    s.naturalSort()
    fmt.Println(s.arr)

}
\$\endgroup\$
3
\$\begingroup\$

How about making getNextStop able to scan strictly descending runs as well:

func (s *sorting) getNextStop(i int) int {
    if i >= len(s.arr) - 1 {
        return i
    }

    if s.arr[i] <= s.arr[i + 1] {
        // Scan ascending run.
        for i < len(s.arr) - 1 && s.arr[i] <= s.arr[i + 1] {
            i += 1
        }
    } else {
        start := i

        // Scan STRICTLY descending run. We demand strictly
        // descending runs in order to keep the algorithm
        // stable.
        for i < len(s.arr) - 1 && s.arr[i] > s.arr[i + 1] {
            i += 1
        }

        end := i

        for start < end {    
            s.arr[start], s.arr[end] = s.arr[end], s.arr[start]
            start += 1
            end -= 1
        }
    }

    return i 
}

That way, you drastically reduce the amount of runs in the array, and, thus, increase performance. Also, if you think about it, your implementation is not a natural mergesort: you merge the second run with the first one, then you merge the third run with the first/second, the fourth run with first/second/third, and so on, so your current implementation is just a fancy insertion sort and may easily degrade to \$\Theta(n^2)\$.

Edit: In order to make your natural "merge sort" a natural merge sort, use:

func (s *sorting) naturalSort() {
    if len(s.arr) <= 1 {
        return
    }

    offset := 0

    for {
        stop1 := s.getNextStop(offset)

        if stop1 == len(s.arr)-1 {

            if offset == 0 {
                // Sorting done.
                return
            } else {
                // Current run is an orphan.
                // Possibly handle it in the
                // next merge pass.
                offset = 0
                continue
            }
        }

        stop2 := s.getNextStop(stop1 + 1)

        s.merge(offset, stop1, stop2)
        offset = stop2 + 1

        if stop2 == len(s.arr)-1 {
            // Proceed to the next merge pass.
            offset = 0
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.