commit 8d57d4272bd4b9af4e5cf472c23440bcb2edac39
parent c1c0b38ac84eeea6bc3dce4b035661b140c9cfba
Author: William Lindholm <william_lindholm@outlook.com>
Date: Fri, 5 Apr 2024 21:43:05 +0200
Removed inefficient O(n) delete index in array function.
Diffstat:
1 file changed, 13 insertions(+), 16 deletions(-)
diff --git a/dsa/merge-sort.go b/dsa/merge-sort.go
@@ -36,37 +36,34 @@ func mergeSort(v []int) []int {
func merge(v1 []int, v2 []int) []int {
var v3 []int
+ v1pos, v2pos := 0, 0 // keeps track of the current index at which the next element should be picked
+
// If both halves contain elements
- for len(v1) > 0 && len(v2) > 0 {
+ for len(v1) > v1pos && len(v2) > v2pos {
if v1[0] < v2[0] {
- v3 = append(v3, v1[0])
- v1 = deleteElement(v1, 0)
+ v3 = append(v3, v1[v1pos])
+ v1pos++
} else {
- v3 = append(v3, v2[0])
- v2 = deleteElement(v2, 0)
+ v3 = append(v3, v2[v2pos])
+ v2pos++
}
}
// If right is empty
- for len(v1) > 0 {
- v3 = append(v3, v1[0])
- v1 = deleteElement(v1, 0)
+ for len(v1) > v1pos {
+ v3 = append(v3, v1[v1pos])
+ v1pos++
}
// If left is empty
- for len(v2) > 0 {
- v3 = append(v3, v2[0])
- v2 = deleteElement(v2, 0)
+ for len(v2) > v2pos {
+ v3 = append(v3, v2[v2pos])
+ v2pos++
}
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) {
