Dumm Sorting Algorims

A collection of humorous and impractical sorting algorithms in Julia.

---

Stalins Sort

Tired of inefficiency inside your sorting allgorithms. I present Stalins sort. With an asymtotic complexety of only \(\mathcal{O}(n)\). The only downside is that some values might end up inside the gulag

function stalins_sort(A::Vector{T})::Vector{T} where T <: Any
  last::T = A[1]
  B = Vector{T}([last])
  for i in 2:length(A)
    if last < A[i]
      push!(B, A[i])
      last = A[i]
    end
  end
  return B
end

println("perfectly sorted array:")
@show stalins_sort([4, 3, 5, 9, 2, 1, 6, 8, 7])
nothing # display nothing

perfectly sorted array:
stalins_sort([4, 3, 5, 9, 2, 1, 6, 8, 7]) = [4, 5, 9]

Random Sort

Why limit oneself to deterministic algorithms? Random sort is a sorting algorithm that randomly shuffles the input until it is sorted. It has an expected time complexity of \(\mathcal{O}(n!)\) but a space complexity of just \(\mathcal{O}(n)\) in nondeterministic machienes.

function random_sort(A::Vector{T})::Vector{T} where T <: Any
  B = copy(A)
  while !issorted(B)
    # shuffle the array
    for i in 1:length(B)
      j = rand(1:length(B))
      B[i], B[j] = B[j], B[i]
    end
  end
  return B
end

println("randomly sorted array:")
@show random_sort([4, 3, 5, 9, 2, 1, 6, 8, 7])
nothing # display nothing

randomly sorted array:
random_sort([4, 3, 5, 9, 2, 1, 6, 8, 7]) = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Miracle Sort

Haters would say that this algorithm never terminates, but experts know that there is a real chance of cosmic rays hitting the computer and flipping enoth bits to make the while condition true and thereby effectivly sorting the array.

function miracle_sort!(A::Vector{T})::Vector{T} where T <: Any
  while !issorted(A)
    # sleep for 1 sec
    sleep(1)
  end
  return A
end

println("sorted array:")
@show miracle_sort!([4, 3, 5, 9, 2, 1, 6, 8, 7])
nothing # display nothing

still running...