commit c1c0b38ac84eeea6bc3dce4b035661b140c9cfba
parent 4bb141a2cf73677b4c36c0f96d265b7ea7484158
Author: William Lindholm <william_lindholm@outlook.com>
Date: Fri, 5 Apr 2024 21:33:13 +0200
Merge sort experiment done.
Diffstat:
| A | dsa/merge-sort.go | | | 86 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 86 insertions(+), 0 deletions(-)
diff --git a/dsa/merge-sort.go b/dsa/merge-sort.go
@@ -0,0 +1,86 @@
+package main
+
+import (
+ "bytes"
+ "fmt"
+ "math"
+)
+
+func main() {
+ v := []int{9, 8, 6, 3, 1, 0, 11, 4}
+ printArr(v)
+ printArr(mergeSort(v))
+}
+
+// MergeSort O(n * log(n))
+func mergeSort(v []int) []int {
+
+ if len(v) == 1 {
+ return v
+ }
+
+ q1 := 0
+ q2 := int(math.Ceil(float64(len(v)) / 2))
+ q3 := len(v)
+
+ v1 := v[q1:q2]
+ v2 := v[q2:q3]
+
+ v1 = mergeSort(v1)
+ v2 = mergeSort(v2)
+
+ return merge(v1, v2)
+}
+
+// Merge the two halves of the mergeSort.
+func merge(v1 []int, v2 []int) []int {
+ var v3 []int
+
+ // If both halves contain elements
+ for len(v1) > 0 && len(v2) > 0 {
+ if v1[0] < v2[0] {
+ v3 = append(v3, v1[0])
+ v1 = deleteElement(v1, 0)
+ } else {
+ v3 = append(v3, v2[0])
+ v2 = deleteElement(v2, 0)
+ }
+ }
+
+ // If right is empty
+ for len(v1) > 0 {
+ v3 = append(v3, v1[0])
+ v1 = deleteElement(v1, 0)
+ }
+
+ // If left is empty
+ for len(v2) > 0 {
+ v3 = append(v3, v2[0])
+ v2 = deleteElement(v2, 0)
+ }
+
+ return v3
+}
+
+// Delete an element at position and shift to right
+func deleteElement(slice []int, index int) []int {
+ return append(slice[:index], slice[index+1:]...)
+}
+
+// print an []int array
+func printArr(v []int) {
+
+ var buffer bytes.Buffer
+ buffer.WriteString("{")
+
+ for i, n := range v {
+ buffer.WriteString(fmt.Sprintf("%d", n))
+ if i < len(v)-1 {
+ buffer.WriteString(", ")
+ }
+ }
+
+ buffer.WriteString("}")
+
+ fmt.Println(buffer.String())
+}
