Can somebody review this code:

Getting Help Code Review
1

I wrote a naive sorting algorithm, but it works too well (it sorts an array of 1,000,000,000 values in 3 seconds). Based on my assumptions, it has a time complexity of O(n) and a space complexity of O(n) in big O notation.I most likely made a mistake somewhere, so please tell me what it is.

func UnNamedSort(arr []int) []int {
	min_idx := 0
	for i := 0; i < len(arr); i++ {
		if arr[i] < arr[min_idx] {
			arr[i], arr[min_idx] = arr[min_idx], arr[i]
			min_idx = i
		}
	}
	return arr
}
2

I want to preface this by saying I am mostly a pragmatic programmer with experience in writing web APIs, not algorithms. But a couple things to consider here: how many times would you need to recursively call this to sort certain arrays? Let’s create a function to test it:

const maxRetries = 10

func SortUntilDesiredResult(items []int, desiredResult []int, numPasses int) {
	if numPasses > maxRetries {
		fmt.Println("Hit max retries. Can't sort")
		return
	}
	sorted := UnNamedSort(items)
	for i := 0; i < len(items); i++ {
		if items[i] != desiredResult[i] {
			fmt.Println("Want", desiredResult, "Got", sorted, "recursively calling sort function")
			SortUntilDesiredResult(sorted, desiredResult, numPasses+1)
			return
		}
	}
	fmt.Println("Want", desiredResult, "Got", sorted, "It took", numPasses, "passes")
}

We can see O(n) is quickly out the window in this worst case scenario:

items := []int{5, 4, 3, 2, 1}
desiredResult := []int{1, 2, 3, 4, 5}
SortUntilDesiredResult(items, desiredResult, 1)

… which yields:

Want [1 2 3 4 5] Got [4 3 2 1 5] recursively calling sort function
Want [1 2 3 4 5] Got [3 2 1 4 5] recursively calling sort function
Want [1 2 3 4 5] Got [2 1 3 4 5] recursively calling sort function
Want [1 2 3 4 5] Got [1 2 3 4 5] It took 4 passes

You can see the numbers slowly moving towards sorted position. What happens to our complexity for each number added to the array in this case? Second, I believe there’s a bug in the logic for cases when the first item is also the smallest. Consider this:

items := []int{3, 4, 5, 2, 1}
desiredResult := []int{1, 2, 3, 4, 5}
SortUntilDesiredResult(items, desiredResult, 1)

… which yields:

Want [1 2 3 4 5] Got [2 4 5 1 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Want [1 2 3 4 5] Got [1 4 5 2 3] recursively calling sort function
Hit max retries. Can't sort

Anyway, there could be a bug in my testing logic. I believe this is more or less an implementation (minus the bug I noted) of bubble sort so worst case is O(n2). Also if you’re interested in this stuff, Grokking Algorithms is a great book. Anyway, somebody with more daily experience in this feel free to correct me if I’m wrong! Also here’s a playground link:

3

Unlikely… As far as I remember it has been mathematically proven that the lower bound is O(n log n).

4

Thank you so much. I noticed a bug in my tests that prevented me from seeing the algorithm’s malfunction