Sort numbers using Goroutines

Hello, I’m learning Go by doing some exercises, I have this exercise where I should sort numbers from an input and use Go Routines, so let’s don’t talk about the purpose or my algorithm, it’s just exploration.

I’ll explain my problem in the buttom
Here is my code, you cannot use it on Google Playground since my code require some inputs.

package main

import (
	"fmt"
	"sort"
)

func divideList(list []int, cut int) (tmp, s []int) {
	tmp = append(list[cut:])
	s = append(list[:cut])
	return tmp, s
}

func sortList(list []int, c chan []int) {
	sort.Ints(list)
	c <- list
}

func main() {
	// define the size of the number we want to sort
	size := 5

	// put the number list into a slice
	list := []int{-9, -11, 12, 13, 9}
	fmt.Println("Your digits input : ", list)

	// divide the number list into 4 different slices
	cut := size / 4
	list, s1 := divideList(list, cut)
	cut = len(list) / 3
	list, s2 := divideList(list, cut)
	cut = len(list) / 2
	list, s3 := divideList(list, cut)
	s4 := list

	// sort in different go routines
	c := make(chan []int, 4)
	go sortList(s1, c)
	go sortList(s2, c)
	go sortList(s3, c)
	go sortList(s4, c)

	sortedS1 := <-c
	sortedS2 := <-c
	sortedS3 := <-c
	sortedS4 := <-c

	fmt.Println(sortedS1)
	fmt.Println(sortedS2)
	fmt.Println(sortedS3)
	fmt.Println(sortedS4)
	fmt.Println("-----------------------")

	// merge the 4 sorted slices
	sortedList1 := append(sortedS1, sortedS2...)
	fmt.Println(sortedList1)
	sortedList2 := append(sortedS3, sortedS4...)
	fmt.Println(sortedList2)
	finalList := append(sortedList1, sortedList2...)
	fmt.Println(finalList)

	// we need to sort it again
	sort.Ints(finalList)
	fmt.Println("Here your digits sorted: ", finalList)
}

And here is my result (maybe you should try multiple times to get the problem)

How many integer do you want to sort? 5
Please type all your digits you want to sort and press Enter: -9 -11 12 13 9
Your digits input :  [-9 -11 12 13 9]
[-9]
[12]
[9 13]
[-11]
-----------------------
[-9 12]
[9 13 12]
[-9 12 9 13 12]
Here your digits sorted:  [-9 9 12 12 13]

Process finished with exit code 0

Look at the part after this comment : // merge the 4 sorted slices
The problem is I am merging 4 slices, since we cannot merge them at once, I merged them by two but I can’t see why my results is different.

For this part the result is ok
sortedList1 := append(sortedS1, sortedS2...)
merging [-9] with [12] and nice I have [-9 12]

but this part
sortedList2 := append(sortedS3, sortedS4...)
I am merging [9 13] with [-11] and I have [9 13 12]
Obviously it merge with another slice but why?
I know it’s not the best algorithm but I need to understand the problem.
This happned to me using Goland on Windows, I prefer largely to work on linux but I am trying GoLand IDE.

If someone could explain the problem that would be awsome remember that you need to run code multiple time to get the problem, cause sometimes its sort well.

If you do

sort.Ints(finalList)

why not

just do

sort.Ints(list)

and skip all the steps in between?

1 Like

The purpose of the exercise is to learn how Go routines work, it says that I have to split the slice in 4 and sort each slice using Go routine, I know it’s nonsense we can just sort the whole slice and done.

I totally understand that’s the algorithm is little annoying, but as I said let’s just put the purpose of the exercise aside and try to understand why I have a problem with this append.

I’m still doing some test and I keep you informed if I found something

You can set value for slice in code and not enter them all the time for testing:

	// define the size of the number we want to sort
	size := 5

	// put the number list into a slice
	list := []int{-9, -11, 12, 13, 9}

I don’t see anything wrong in your code, although that part doesn’t make any sense:

	tmp = append(list[cut:])
	s = append(list[:cut])

Maybe you can ask the question on SO.

2 Likes

Since I hard code the input, I tried the code on Go playground and I have always the good result but in GoLand I still have the bad results sometimes

You are totally right, I’m gonna edit that part

What is SO?

this part is to split the slice in 4 slices

SO is stackoverflow - https://stackoverflow.com
I don’t like SO, but there are several strong Go developers who answer there.

1 Like

Of course StackOverflow, how I didn’t guess that.
I m gonna do some test and I will try SO thank you

I mean you can just return parts:
return list[cut:], list[:cut]
Your append doing nothing.

2 Likes

Oh didn’t know that! thank you :slight_smile:

All right good new someone on SO found the problem
Now I’m 100% sure that it was about the allocation of length/capacity of my slices which make the append faulty.
Yes the problem happen on the last append
The key information is here

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large underlying array that fits both the existing slice elements and the additional values. Otherwise, append re-uses the underlying array.

The functionality of the slice and underlying array is still blury in my mind, if think about some exercises or website who can make this perfectly clear, I’ll be more happy to learn from that.

1 Like

But why the behaviour is changes time to time? What part is undefined behaviour?

1 Like

Good question, the different result is because of the race condition of the Go routines, I have 4 go routines and every time one of them append first.

There is a good article about this, that I just found :slight_smile:

I just want to add more info about it. Just in case
The problem was indeed on the allocation of slice, I thought slice mechanism work exactly like an array but I forgot that slice are like a window to an array.
The slice had a bigger capacity in a same array, my go routines were appending on that array in different order each time I run the code. That’s why I had different result.

here is the correct code, I added length and capacity in the end of the result so you can see they were properly allocated.

Keep in mind that this code is not optimal, we can do way much better.

package main

import (
	"fmt"
	"sort"
	"strconv"
)

func send(list []int, c chan []int) {
	sort.Ints(list)
	c <- list
}

// Split integers.
func split(list []int) (tmpS []int, splS []int) {
	halfSize := len(list)/2
	tmpSize := len(list) - halfSize
	tmpS = make([]int, tmpSize)
	splS = make([]int, halfSize)
	copy(tmpS, list[halfSize:])
	copy(splS, list[:halfSize])
	fmt.Println(tmpS, splS)
	return tmpS, splS
}

func convert(sStr []string) (sInt []int) {
	sInt = make([]int, 0, cap(sStr))
	for _, r := range sStr {
		digit, _ := strconv.Atoi(r)
		sInt = append(sInt, digit)
	}
	fmt.Println("Sorted sub array: ", sInt)
	return sInt
}

func main() {
	list := []string{"-9", "-11", "12", "13", "9"}
	fmt.Println("Your unsorted digits: ", list)

	// Convert the whole slice
	sInt := convert(list)

	splS1, splS2 := split(sInt)
	splS11, splS12 := split(splS1)
	splS21, splS22 := split(splS2)

	// Send in different go routines.
	c := make(chan []int)
	go send(splS11, c)
	go send(splS12, c)
	go send(splS21, c)
	go send(splS22, c)

	// Receive from a channel.
	sortedS1 := <-c
	sortedS2 := <-c
	sortedS3 := <-c
	sortedS4 := <-c

	fmt.Printf("sortedS1 - Length: %d Capacity: %d\n", len(sortedS1), cap(sortedS1))
	fmt.Printf("sortedS2 - Length: %d Capacity: %d\n", len(sortedS2), cap(sortedS2))
	fmt.Printf("sortedS3 - Length: %d Capacity: %d\n", len(sortedS3), cap(sortedS3))
	fmt.Printf("sortedS4 - Length: %d Capacity: %d\n", len(sortedS4), cap(sortedS4))

	// Merge the 4 sorted slices.
	sortedList1 := append(sortedS1, sortedS2...)
	sortedList2 := append(sortedS3, sortedS4...)
	finalList := append(sortedList1, sortedList2...)

	// Sort it again
	sort.Ints(finalList)
	fmt.Println("Here your digits sorted: ", finalList)
}

Thank you for everything

1 Like