Sorting Algorithm Theory VS Implementation 🧐 ?
Tags: algorithms, programming, discuss, showdev
Published: 2024-01-07 14:44:19

## Why Sorting?

I started **learning Golang** last week and to solidify my understanding of the syntax, I practiced using Leetcode. This led me to revisit the algorithms I learned in my university years, which I had long forgotten. The merge sort algorithm, in particular, sparked my interest and motivated me to learn more about sorting.

Here are the references for the sorting algorithm:
- **Bubble Sort**, which had the time complexity of (n^2)
    - more on bubble sort https://www.geeksforgeeks.org/bubble-sort/
- **Merge Sort**, which had the time complexity of (n * log(n))
    - more on merge sort https://www.geeksforgeeks.org/merge-sort/
- **Quick Sort**, which had the time complexity of (n * log(n))
    - more on quick sort https://www.geeksforgeeks.org/quick-sort/

Since **people rarely use bubble sort** due to its time complexity and perhaps because they prefer to use the built-in sort function, **I wonder how inefficient it actually is** . Thus to find out, I conducted a simple experiment.

## Experiment

The **experiment** aims to **track the time** needed for the `merge`, `bubble`, `quick`, and `built-in` (`sort.Ints`) sorting function **to sort the array**. The whole experiment setup can be seen on my GitHub repo

{% embed https://github.com/peterchu999/sorting-experiment %}

This is how the time tracking works:

```go
func TestSorting(sfc SortFunction, arr []int) int64 {
	scopedTestList := make([]int, len(arr)) 
	copy(scopedTestList, arr) // copy the unsorted array to avoid side effects on other test
	startTime := time.Now() // track start time
	sfc(scopedTestList) // call sorting function
	endTime := time.Now() // track end time
	return endTimeMerge.Sub(startTimeMerge).Nanoseconds() // test return startTime - endTime
}
```
And here is the test setup:
```go
for i:=1; i < arrLen+1; i++ {
	testCase := GenerateUniqueRandomNumbers, 100) // generate i length of random numbers array
	mergeT := utils.TestSorting(MergeSortVoid, testCase)
	time.Sleep(time.Millisecond * 5) // incase computation degrade machine and make later case worst
	bubbleT := utils.TestSorting(BubbleSortVoid, testCase)
	time.Sleep(time.Millisecond * 5) // incase computation degrade machine and make later case worst
	quickT := utils.TestSorting(QuickSortVoid, testCase)
	time.Sleep(time.Millisecond * 5) // incase computation degrade machine and make later case worst
	biT :=  utils.TestSorting(sort.Ints, testCase)
}
```
- loop until `arrLen` which was the maximum number of the array length.
- for each iteration, generate a random number array with the length of the current iteration index (i)
- for each iteration, tracked the time needed for each sorting function to sort the array

the gathered data from the experiment above were saved and visualized by using Python code. The **visualization plot the time taken** for **each array length** to be **sorted**. 

## Result

Interesting results are shown when using a small array length. **Let's examine the visualized graph comparing the complexity of theoretical sorting algorithms with the actual implementation time**.

![theory visualization of 50 array length](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lx6und2z4bf31q11kpc5.png)


![sort experiment visualization of 50 array length](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/14cx4ptsa74oerr2kwr0.png)


**Up to** an **array length** of around **30**, **bubble sort**, which was **presumably** deemed **slower** according to theory, was **actually faster** than the `merge` and `built-in` sort functions. It's quite surprising 🤯 !

However, when we **look at the bigger picture**, the **theory and implementation align** . Here is the visualization of the theoretical sort complexity versus the sort implementation time for an array length of 1000.

![theory visualization of 1000 array length](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rnsc3zsz8p65ase580xz.png)

![sort experiment visualization of 1000 array length](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t7nc0320zctjb4sgpl1m.png)

## Conclusion

In the end, **when the array size is small**, the sorting operation **takes a very short amount of time** (just a few nanoseconds), so **no one really notices the difference**. **What truly matters is that the `n * log(n)` sort algorithm** (merge sort, quick sort) we learned **performs significantly better on larger array size**. 

Please check out my [code](https://github.com/peterchu999/sorting-experiment) and feel free to experiment with it. **If you find any flaws or errors, please create an issue on GitHub or leave a comment 💬 below!**

I'm still **unsure why bubble sort performs better on small datasets**. **My guess** is that **the operation to create a new array** in merge sort **takes longer than** simply **swapping values** between indices. What do you think 🤔 ? **Please share your thoughts and comments 🙌!**


### Acknowledgment
- https://unsplash.com/photos/long-exposure-photography-of-road-and-cars-NqOInJ-ttqM (cover image)
- https://geeksforgeeks.org/
- https://blog.boot.dev/golang/quick-sort-golang/ (quick sort)
- https://www.tutorialspoint.com/how-to-generate-a-array-of-unique-random-numbers-in-golang (generate random number array)