golanglabs

Log | Files | Refs | README | LICENSE

merge_sort.go (886B)

      1 package dsa
      2 
      3 import (
      4 	"math"
      5 )
      6 
      7 // MergeSort O(n * log(n))
      8 func MergeSort(v []int) []int {
      9 
     10 	if len(v) == 1 {
     11 		return v
     12 	}
     13 
     14 	q1 := 0
     15 	q2 := int(math.Ceil(float64(len(v)) / 2))
     16 	q3 := len(v)
     17 
     18 	v1 := v[q1:q2]
     19 	v2 := v[q2:q3]
     20 
     21 	v1 = MergeSort(v1)
     22 	v2 = MergeSort(v2)
     23 
     24 	return merge(v1, v2)
     25 }
     26 
     27 // Merge the two halves of the mergeSort.
     28 func merge(v1 []int, v2 []int) []int {
     29 	var v3 []int
     30 
     31 	v1pos, v2pos := 0, 0 // keeps track of the current index at which the next element should be picked
     32 
     33 	// If both halves contain elements
     34 	for len(v1) > v1pos && len(v2) > v2pos {
     35 		if v1[v1pos] < v2[v2pos] {
     36 			v3 = append(v3, v1[v1pos])
     37 			v1pos++
     38 		} else {
     39 			v3 = append(v3, v2[v2pos])
     40 			v2pos++
     41 		}
     42 	}
     43 
     44 	// If right is empty
     45 	for len(v1) > v1pos {
     46 		v3 = append(v3, v1[v1pos])
     47 		v1pos++
     48 	}
     49 
     50 	// If left is empty
     51 	for len(v2) > v2pos {
     52 		v3 = append(v3, v2[v2pos])
     53 		v2pos++
     54 	}
     55 
     56 	return v3
     57 }