Created
November 27, 2019 03:13
-
-
Save hasufell/2f7146e39291a5eb3c5560c8f82b7c55 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package sort | |
import ( | |
"context" | |
"fmt" | |
) | |
// Merge too already sorted and deduplicated lists. | |
func MergeLists(l []int, r []int) []int { | |
n := []int{} | |
i := 0 | |
j := 0 | |
for { | |
if i == len(l) && j == len(r) { | |
break | |
} else if i == len(l) { | |
n = append(n, r[j:]...) | |
break | |
} else if j == len(r) { | |
n = append(n, l[i:]...) | |
break | |
} | |
if l[i] < r[j] { | |
n = append(n, l[i]) | |
i++ | |
} else if l[i] > r[j] { | |
n = append(n, r[j]) | |
j++ | |
} else if l[i] == r[j] { | |
n = append(n, l[i]) | |
i++ | |
j++ | |
} | |
} | |
return n | |
} | |
// Mergesorts and deduplicates the list. | |
func SortedAndDedup(ctx context.Context, list []int) (res []int, err error) { | |
sorted, err := Mergesort(ctx, list) | |
if err != nil { | |
return nil, err | |
} | |
deduped := dedupSortedList(sorted) | |
return deduped, nil | |
} | |
// Deduplicate the sorted list and return a new one with a potentially different | |
// size. | |
func dedupSortedList(list []int) []int { | |
newList := []int{} | |
if len(list) <= 1 { | |
return list | |
} | |
var prev int = list[0] | |
newList = append(newList, list[0]) | |
for i := 1; i < len(list); i++ { | |
if prev != list[i] { | |
newList = append(newList, list[i]) | |
} | |
prev = list[i] | |
} | |
return newList | |
} | |
// Mergesorts the given list and returns it as a result. The input list | |
// is not modified. | |
// The algorithm is a bottom-up iterative version and not explained | |
// in detail here. | |
func Mergesort(ctx context.Context, list []int) (res []int, err error) { | |
newList := append([]int{}, list...) | |
temp := append([]int{}, list...) | |
n := len(newList) | |
for m := 1; m < (n - 1); m = 2 * m { | |
for i := 0; i < (n - 1); i += 2 * m { | |
select { | |
case <-ctx.Done(): | |
return nil, fmt.Errorf("Sorting timed out") | |
default: | |
} | |
from := i | |
mid := i + m - 1 | |
to := min(i+2*m-1, n-1) | |
merge(ctx, newList, temp, from, mid, to) | |
} | |
} | |
return newList, nil | |
} | |
// The merge part of the mergesort. | |
func merge(ctx context.Context, list []int, temp []int, from int, mid int, to int) { | |
k := from | |
i := from | |
j := mid + 1 | |
for i <= mid && j <= to { | |
if list[i] < list[j] { | |
temp[k] = list[i] | |
i++ | |
} else { | |
temp[k] = list[j] | |
j++ | |
} | |
k++ | |
} | |
for i <= mid && i < len(temp) { | |
temp[k] = list[i] | |
i++ | |
k++ | |
} | |
for i := from; i <= to; i++ { | |
list[i] = temp[i] | |
} | |
} | |
// Get the minimum of two integers. | |
func min(l int, r int) int { | |
if l < r { | |
return l | |
} else { | |
return r | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment