Natural mergesort

Question

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)

}

Answer 1

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
        }
    }
}