diff options
| -rw-r--r-- | sort/merge.go | 21 | ||||
| -rw-r--r-- | sort/parallelmerge.go | 4 |
2 files changed, 13 insertions, 12 deletions
diff --git a/sort/merge.go b/sort/merge.go index 9ee788d..86eb315 100644 --- a/sort/merge.go +++ b/sort/merge.go @@ -6,33 +6,34 @@ import ( func Merge(a ds.ArrayList) ds.ArrayList { aux := make(ds.ArrayList, len(a)) - mergeSort(a, aux, 0, len(a)-1) + mergeSort(a, aux) return a } -func mergeSort(a, aux ds.ArrayList, lo, hi int) { - if lo >= hi { +func mergeSort(a, aux ds.ArrayList) { + length := len(a) + if length <= 1 { return } - mid := lo + (hi-lo)/2 - mergeSort(a, aux, lo, mid) - mergeSort(a, aux, mid+1, hi) - merge(a, aux, lo, mid, hi) + mi := length / 2 + mergeSort(a[0:mi], aux[0:mi]) + mergeSort(a[mi:], aux[mi:]) + merge(a, aux, 0, mi-1, length-1) } -func merge(a, aux ds.ArrayList, lo, mid, hi int) { +func merge(a, aux ds.ArrayList, lo, mi, hi int) { for i := lo; i <= hi; i++ { aux[i] = a[i] } i := lo - j := mid + 1 + j := mi + 1 for k := lo; k <= hi; k++ { switch { - case i > mid: + case i > mi: a[k] = aux[j] j++ case j > hi: diff --git a/sort/parallelmerge.go b/sort/parallelmerge.go index b6cf721..577d7c1 100644 --- a/sort/parallelmerge.go +++ b/sort/parallelmerge.go @@ -17,8 +17,8 @@ func parallelMerge(a, aux ds.ArrayList, lo, hi int) { defer merge(a, aux, lo, mid, hi) if hi-lo <= 1000 { - mergeSort(a, aux, lo, mid) - mergeSort(a, aux, mid+1, hi) + //mergeSort(a, aux, lo, mid) + //mergeSort(a, aux, mid+1, hi) return } |