I’m implementing basically the Median of Medians (actually, Median of Ninthers) algorithm for quick deterministic selection (see [original post]). It is recursive, as in the way to find a pivot is by calculating the median of ninthers of chunks of the array and that median is found by calling the `medianofninthers`

of those ninthers.

I keep reading that Julia is not great with recursion and that TCO is not well supported, and that I should make the calls iterative instead of recursive, but then I see that Quick Sort implementation (which in essence is very similar to median of medians, but with a different pivot finding algorithm and of course without sorting) is recursive.

If I could gain some clarity on what the right approach is here, I’d really appreciate it!

For reference, this is the `medianofmedians!`

function and the functions it calls (the recursion happens between `quickselect!`

and `medianofmedianspartition!`

, but I include `hoarepartition!`

and `medianoffive!`

for completeness, note that only hoarepartition uses inbounds macro because i’m still learning how and where to use).

(note: In the last post I was asked to add more code, please let me know if I’m going overboard here, I’m still figuring out the etiquette here.)

```
function medianofmedianspartition!(arr::AbstractVector)
len = length(arr)
if len < 5
sort!(arr)
return 1 + len ÷ 2
end
j = 1
i = 1
while i + 4 <= len
arr_view = @view(arr[i:(i+4)])
medianoffive!(arr_view)
arr[j], arr_view[3] = arr_view[3], arr[j]
i += 5
j += 1
end
j -= 1
quickselect!(@view(arr[1:j]), 1 + j ÷ 2, medianofmedianspartition!)
return hoarepartition!(arr, 1 + j ÷ 2)
end
function quickselect!(arr::AbstractVector, position::Integer, partitionfunc!::Function)
i = 1
j = length(arr)
if i == j
return
end
while true
new_position = i + partitionfunc!(@view(arr[i:j])) - 1
if new_position == position
return
elseif new_position > position
j = new_position - 1
else
i = new_position + 1
end
end
return
end
function hoarepartition!(arr::AbstractVector, pivot_index::Integer)
@inbounds pivot_value = arr[pivot_index]
@inbounds arr[pivot_index], arr[1] = arr[1], arr[pivot_index]
a = 2
b = length(arr)
@inbounds while a < b
while a <= b && arr[a] <= pivot_value
a += 1
end
while pivot_value < arr[b]
b -= 1
end
if a >= b
break
end
arr[a], arr[b] = arr[b], arr[a]
a += 1
b -= 1
end
@inbounds arr[a-1], arr[1] = arr[1], arr[a-1]
return a - 1
end
function medianoffive!(a::AbstractVector)
@assert length(a) == 5 "medianoffive! only works for arrays of 5 elements."
# We order x1 < x2 and x3 < x4
if a[1] > a[2]
a[1], a[2] = a[2], a[1]
end
if a[3] > a[4]
a[3], a[4] = a[4], a[3]
end
# We remove lowest of first 4 by comparing x1 and x3.
if a[1] < a[3]
a[1], a[5] = a[5], a[1]
if a[1] > a[2]
a[1], a[2] = a[2], a[1]
end
else
a[3], a[5] = a[5], a[3]
if a[3] > a[4]
a[3], a[4] = a[4], a[3]
end
end
# Now we have to find 2nd element out of x1 < x2, x3 < x4
if a[1] < a[3]
if a[2] < a[3]
a[2], a[3] = a[3], a[2]
return
else
return
end
else
if a[4] < a[1]
a[4], a[3] = a[3], a[4]
return
else
a[1], a[3] = a[3], a[1]
return
end
end
return
end
```