/
stable_sort.go
55 lines (48 loc) · 1.64 KB
/
stable_sort.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package sort
import (
"github.com/liyue201/gostl/utils/comparator"
"github.com/liyue201/gostl/utils/iterator"
)
//Stable sorts the container by using merge sort
func Stable[T any](first, last iterator.RandomAccessIterator[T], cmp comparator.Comparator[T]) {
tempSlice := make([]T, last.Position()-first.Position(), last.Position()-first.Position())
mergeSort(first, last, cmp, tempSlice)
}
func mergeSort[T any](first, last iterator.RandomAccessIterator[T], cmp comparator.Comparator[T], tempSlice []T) {
if first.Position()+1 == last.Position() {
return
}
mid := first.IteratorAt((first.Position() + last.Position()) >> 1)
mergeSort(first, mid, cmp, tempSlice)
mergeSort(mid, last, cmp, tempSlice)
merge(first, mid, last, cmp, tempSlice)
}
func merge[T any](first, mid, end iterator.RandomAccessIterator[T], cmp comparator.Comparator[T], tempSlice []T) {
firstIter := (first.Clone()).(iterator.RandomAccessIterator[T])
secondIter := (mid.Clone()).(iterator.RandomAccessIterator[T])
pos := 0
for firstIter.Position() < mid.Position() && secondIter.Position() < end.Position() {
if cmp(firstIter.Value(), secondIter.Value()) <= 0 {
tempSlice[pos] = firstIter.Value()
pos++
firstIter.Next()
} else {
tempSlice[pos] = secondIter.Value()
pos++
secondIter.Next()
}
}
for ; firstIter.Position() < mid.Position(); firstIter.Next() {
tempSlice[pos] = firstIter.Value()
pos++
}
for ; secondIter.Position() < end.Position(); secondIter.Next() {
tempSlice[pos] = secondIter.Value()
pos++
}
iter := first.Clone().(iterator.RandomAccessIterator[T])
for idx := 0; idx < pos; idx++ {
iter.SetValue(tempSlice[idx])
iter.Next()
}
}