Algorithms: 5. Merge Sort

Algorithms: 5. Merge Sort

Mar 20, 2022
programming, go, algorithms, generics

Introduction #

The merge sort is a bit more complicated than the bubble sort and insertion sort as you can see by the code below. In principle the merge sort works by splitting the array in half, and then splitting each of those two parts in half, and then splitting each of those four parts in half, etc, until we have elements of a maximum of two elements. We then sort and merge those elements in a specific order to ensure that the end result is the sorted array we were wanting.

Let’s take this array - [410,821,551,51,638]:

flowchart TD; A([410,821,551,51,638]) --> |1| B([410,821,551]); A([410,821,551,51,638]) --> |7| C([51,638]); B([410,821,551]) --> |2| D([410,821]); B([410,821,551]) --> |5| E([551]); D([410,821]) --> |3| F([410]); D([410,821]) --> |3| G([821]); C([51,638]) --> |8| H([51]); C([51,638]) --> |8| I([638]); F([410]) --> |4| J([410,821]); G([821]) --> |4| J([410,821]); E([551]) --> |6| K([410,551,821]); J([410,821]) --> |6| K([410,551,821]); H([51]) --> |9| L([51,638]) I([638]) --> |9| L([51,638]); K([410,551,821]) --> |10| M([51,410,551,638,821]); L([51,638]) --> |10| M([51,410,551,638,821]); classDef greenClass fill: #9f6, stroke: #333, stroke-width: 2px, color: black; class J,K,L,M greenClass; classDef labelClass border: 2px solid blue, border-radius: 5px; classDef edgeLabel color: black, background-color: white, border-radius: 5px, padding: 5px; linkStyle 0,1,2,3,4,5,6,7,8,9,10,11,1,2,13,14,15 labelClass;

The numbers on the link arrows are the order in which the merge sort happens. So it deals with the left branch before dealing with the right branch, for each branch.

Solution # 

package main

import (
    "flag"
    "fmt"
    "math/rand"

    "golang.org/x/exp/constraints"
)

func merge[T constraints.Ordered](left, right []T) (array []T) {

    array = make([]T, len(left)+len(right))

    var i int64 = 0

    for len(left) > 0 && len(right) > 0 {
        if left[0] < right[0] {
            array[i] = left[0]
            left = left[1:]
        } else {
            array[i] = right[0]
            right = right[1:]
        }

        i++
    }

    for j := 0; j < len(left); j++ {
        array[i] = left[j]
        i++
    }

    for j := 0; j < len(right); j++ {
        array[i] = right[j]
        i++
    }

    return
}

func mergeSort[T constraints.Ordered](array []T) []T {

    var num = int64(len(array))

    if num == 1 {
        return array
    }

    middle := int64(num / 2)

    var (
        i     int64
        left  = make([]T, middle)
        right = make([]T, num-middle)
    )

    for i = 0; i < num; i++ {
        if i < middle {
            left[i] = array[i]
        } else {
            right[i-middle] = array[i]
        }
    }

    return merge(mergeSort(left), mergeSort(right))
}

func randomString(n int) string {

    var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

    s := make([]rune, n)

    for i := range s {
        s[i] = letters[rand.Intn(len(letters))]
    }

    return string(s)
}

func main() {

    var size int
    var intArray []int64
    var floatArray []float64
    var stringArray []string

    // Define the flags and their default values
    flag.IntVar(&size, "size", 100, "The size of the array")
    flag.Parse()

    // Load the input array
    for i := 1; i <= size; i++ {
        intArray = append(intArray, rand.Int63n(1000))
    }

    // Output
    fmt.Printf("Before Sorting : %v\n", intArray)
    fmt.Printf("After Sorting  : %v\n", mergeSort(intArray))

    // Load the input array
    for i := 1; i <= size; i++ {
        floatArray = append(floatArray, float64(rand.Int63n(1000)) / 10)
    }

    // Output
    fmt.Println("---")
    fmt.Printf("Before Sorting : %v\n", floatArray)
    fmt.Printf("After Sorting  : %v\n", mergeSort(floatArray))

    // Load the input array
    for i := 1; i <= size; i++ {
        stringArray = append(stringArray, randomString(5))
    }

    // Output
    fmt.Println("---")
    fmt.Printf("Before Sorting : %v\n", stringArray)
    fmt.Printf("After Sorting  : %v\n", mergeSort(stringArray))
}

Testing #

Now we run go build and test the program

  • Show the usage
./mergesort --help
Usage of ./mergesort:
  -size int
        The size of the array (default 100)
  • Run the program with the default values
./mergesort
Before Sorting : [410 551 821 51 937 320 758 148 216 449 84 287 574 836 515 873 968 91 790 331 273 956 911 637 378 109 72 650 588 971 344 443 623 459 803 739 883 907 932 780 115 716 20 71 652 907 719 62 110 397 105 721 917 712 449 579 333 825 746 734 718 901 704 610 24 717 269 479 269 750 657 923 512 702 655 257 643 301 19 18 694 41 788 21 911 280 343 55 41 453 631 217 631 218 632 514 904 180 500 71]
After Sorting  : [18 19 20 21 24 41 41 51 55 62 71 71 72 84 91 105 109 110 115 148 180 216 217 218 257 269 269 273 280 287 301 320 331 333 343 344 378 397 410 443 449 449 453 459 479 500 512 514 515 551 574 579 588 610 623 631 631 632 637 643 650 652 655 657 694 702 704 712 716 717 718 719 721 734 739 746 750 758 780 788 790 803 821 825 836 873 883 901 904 907 907 911 911 917 923 932 937 956 968 971]
---
Before Sorting : [38.5 82.3 44.1 80.5 25.8 76.5 86.8 8.3 85 37.9 81.2 11.3 57.1 42.2 12.3 18.9 36.4 58.7 63.7 39.9 62.9 24.4 75.2 52.9 82.2 59.9 78.8 51.4 70.6 79.6 61.1 94.3 51.1 78.8 52.9 90 43.8 80.8 55.9 33.5 15.8 90.2 3.9 14.7 39.7 52.9 17.6 33.8 53 7.5 74.1 44.9 95.1 30.4 22.1 57.4 43.9 50 41.2 98.9 66.6 43.6 86.7 70.1 79.3 88.4 75.9 67.9 73.6 37.5 68.7 49.7 4.4 36.5 91.5 41 24.4 24.7 84 42.8 78.6 23.6 80.7 98.9 70 21.8 75.8 91.2 89.7 74.9 65.6 65 14 15 18.2 8 21.3 45 5.6 24]
After Sorting  : [3.9 4.4 5.6 7.5 8 8.3 11.3 12.3 14 14.7 15 15.8 17.6 18.2 18.9 21.3 21.8 22.1 23.6 24 24.4 24.4 24.7 25.8 30.4 33.5 33.8 36.4 36.5 37.5 37.9 38.5 39.7 39.9 41 41.2 42.2 42.8 43.6 43.8 43.9 44.1 44.9 45 49.7 50 51.1 51.4 52.9 52.9 52.9 53 55.9 57.1 57.4 58.7 59.9 61.1 62.9 63.7 65 65.6 66.6 67.9 68.7 70 70.1 70.6 73.6 74.1 74.9 75.2 75.8 75.9 76.5 78.6 78.8 78.8 79.3 79.6 80.5 80.7 80.8 81.2 82.2 82.3 84 85 86.7 86.8 88.4 89.7 90 90.2 91.2 91.5 94.3 95.1 98.9 98.9]
---
Before Sorting : [LOpbU OpEdK updOM eRVja RzLNT XYeUC WKsXb GyRAO mBTvK SJfjz aLbtZ syMGe uDtRz QMDQi YCOhg HOvgS eycJP JHYNu fNjJh hjUVR uSqfg qVMkP YVkUR UpiFv IZRgB myArK Ctzkj kZIva BjMkX VbWGv bqzge xyALB sdjSG pngCw FkDif IBuuf FMoWd iTskZ oQJMq rTICT ojIYx yeSxZ yfroR ODMbN DRZnP NRWCJ PMHDt JmHAY ORsUf UMAps VgzHb lmYYt EjVgw fFbbG Gcnqb aEREu nUZjQ XmZOt aRLUt mYgmS VYBAD DvoxI fsfgP yCKmx IubeY TNDtj AyRRD edMiy Lpruc jiOgj hYeVw BTCML frDGX qwpzw VGqMZ cLVCx aSJlD SYEof kkEYe qkKHq gBpnb PbgHM LUIDj UMmpB HCSjM Jjxzu aiIsN BakqS wQpOQ gNczg aczAI nLqLI bAatL YHdao povFO kqIex sFzXz rlczt xcdJJ FuyZH]
After Sorting  : [AyRRD BTCML BakqS BjMkX Ctzkj DRZnP DvoxI EjVgw FMoWd FkDif FuyZH Gcnqb GyRAO HCSjM HOvgS IBuuf IZRgB IubeY JHYNu Jjxzu JmHAY LOpbU LUIDj Lpruc NRWCJ ODMbN ORsUf OpEdK PMHDt PbgHM QMDQi RzLNT SJfjz SYEof TNDtj UMAps UMmpB UpiFv VGqMZ VYBAD VbWGv VgzHb WKsXb XYeUC XmZOt YCOhg YHdao YVkUR aEREu aLbtZ aRLUt aSJlD aczAI aiIsN bAatL bqzge cLVCx eRVja edMiy eycJP fFbbG fNjJh frDGX fsfgP gBpnb gNczg hYeVw hjUVR iTskZ jiOgj kZIva kkEYe kqIex lmYYt mBTvK mYgmS myArK nLqLI nUZjQ oQJMq ojIYx pngCw povFO qVMkP qkKHq qwpzw rTICT rlczt sFzXz sdjSG syMGe uDtRz uSqfg updOM wQpOQ xcdJJ xyALB yCKmx yeSxZ yfroR]
  • Run the program and test the size parameter
./mergesort --size=10
Before Sorting : [410 551 821 51 937 320 758 148 216 449]
After Sorting  : [51 148 216 320 410 449 551 758 821 937]
---
Before Sorting : [8.4 28.7 57.4 83.6 51.5 87.3 96.8 9.1 79 33.1]
After Sorting  : [8.4 9.1 28.7 33.1 51.5 57.4 79 83.6 87.3 96.8]
---
Before Sorting : [tcuAx hxKQF DaFpL SjFbc XoEFf RsWxP LDnJO bCsNV lgTeM aPEZQ]
After Sorting  : [DaFpL LDnJO RsWxP SjFbc XoEFf aPEZQ bCsNV hxKQF lgTeM tcuAx]
  • Run the program with an invalid value for the size
./mergesort -size -1.0
invalid value "-1.0" for flag -size: parse error
Usage of ./mergesort:
  -size int
        The size of the array (default 100)
  • Run the program with an invalid flag
./mergesort --sized 10
flag provided but not defined: -sized
Usage of ./mergesort:
  -size int
        The size of the array (default 100)