Top-down Merge Sort
Pseudocode:
func Merge(s []int) {
aux := make([]int, len(s))
var sort func(s S)
sort = func(s S) {
if len(s) <= 1 {
return
}
m := len(s) / 2
sort(s[:m])
sort(s[m:])
merge.MergeInto(s[:m], s[m:], cmp, aux)
copy(s, aux)
}
sort(s)
}The function merge.MergeInto is an implementation of binary merge algorithm, that stores the result into the provided aux
Bottom-up Merge Sort
Bottom-up merge sort eliminates recursion by using an iterative approach, which avoids the risk of stack overflow
Pseudocode:
func MergeBU(s []int) {
n := len(s)
aux := make([]int, n)
for sz := 1; sz < n; sz *= 2 {
for l := 0; l < n-sz; l += 2 * sz {
m, r := l+sz, min(l+2*sz, n)
merge.MergeInto(s[l:m], s[m:r], cmp, aux)
copy(s[l:r], aux)
}
}
}The function merge.MergeInto is an implementation of binary merge algorithm, that stores the result into the provided aux
Sorting Linked Lists
A bottom-up mergesort is the method of choice for sorting data organized in a linked list . Consider the list to be sorted sublists of size 1, then pass through to make sorted subarrays of size 2 linked together, then size 4, and so forth. This method rearranges the links to sort the list in place (without creating any new list nodes)
Properties
| Worst Time | Average Time | Best Time | Worst Space | Average Space | Stability | Adaptive |
|---|---|---|---|---|---|---|
| Stable | Non Adaptive |