Concurrency Merge Sort Using Channels and Goroutines in Golang

Merge sort is a divide and conquer algorithm used to sort a list of elements. The algorithm starts by dividing the unsorted list into n sublists, each containing one element. The sublists are then merged in a manner that results in a sorted list. The merging process involves comparing the elements of the sublists and arranging them in the correct order. The time complexity of merge sort is O(n log n), making it an efficient sorting algorithm for large lists.
Optimize sorting with concurrent Merge Sort using channels and goroutines in Go.

func Mergech(left chan int, right chan int, c chan int) {
    defer close(c)
    val, ok := <-left
    val2, ok2 := <-right
    for ok && ok2 {
        if val < val2 {
            c <- val
            val, ok = <-left
        } else {
            c <- val2
            val2, ok2 = <-right
        }
    }
    for ok {
        c <- val
        val, ok = <-left
    }
    for ok2 {
        c <- val2
        val2, ok2 = <-right
    }
}
func MergeSort(arr []int, ch chan int) {
    if len(arr) < 2 {
        ch <- arr[0]
        defer close(ch)
        return
    }
    left := make(chan int)
    right := make(chan int)
    go MergeSort(arr[len(arr)/2:], left)
    go MergeSort(arr[:len(arr)/2], right)
    go Mergech(left, right, ch)
}
func main() {
    a := []int{5,4,3,2,1}
    c := make(chan int)
    var wg sync.WaitGroup
    wg.Add(1)
    go func() {
        defer wg.Done()
        mergeSort(a, c)
    }()
    wg.Wait()
    var s []int
    for v := range c {
        s = append(s, v)
    }
    fmt.Println(s)
}

Blog

Concurrency Merge Sort Using Channels and Goroutines in Golang

vinay

Join Our Newsletter. No Spam, Only the good stuff.

Related