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 nd two  arrays to merge: nd a sorted subarray (by incrementing a pointer  until nding an entry that is smaller than its predecessor in the  array), then nd the next, then merge them.The code needs to be reviewed for:Correct use of GoAny improvements to the code// NaturalMergeSort.gopackage mainimport (    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)}
Natural mergesort
algorithm;sorting;mergesort;go
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        }    }}