# Can somebody review this code:

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
}
``````

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:

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

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