# Natural mergesort

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

}


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