Comparison-optimal sorting algorithm for five elements, plus testing code. (via Knuth TAoCP Vol 3, 2nd ed, 5.3.1)

optimal_five_sort.rb

def swap(a, i, j) 
  t = a[i]
  a[i] = a[j]
  a[j] = t
end

def sort(a) 
  # Sort first two pairs
  swap(a,0,1) if a[1] < a[0]
  swap(a,2,3) if a[3] < a[2]
  
  # Sort pairs by larger element
  if a[3] < a[1]
    a = a[2,2] + a[0,2] + a[4,1]
  end
    
  # A = [a,b,c,d,e] with a < b < d and c < d
  
  # insert e into [a,b,d]
  if ( a[4] < a[1] ) # e < b
    if ( a[4] < a[0] ) # e < a
      b = a[4,1] + a[0,2] + a[3,1] # B = [e,a,b,d]
    else # e > a
      b = a[0,1] + a[4,1] + a[1,1] + a[3,1] # B = [a,e,b,d]
    end
  else # e > b
    if ( a[4] < a[3] ) # e < d
      b = a[0,2] + a[4,1] + a[3,1] # B = [a,b,e,d]
    else # e > d
      b = a[0,2] + a[3,2] # B = [a,b,d,e]
    end
  end
  
  # insert c into the first three elements of B
  if a[2] < b[1]
    if a[2] < b[0]
      c = a[2,1] + b
    else
      c = b[0,1] + a[2,1] + b[1,3]
    end
  else
    if a[2] < b[2]
      c = b[0,2] + a[2,1] + b[2,2]
    else
      c = b[0,3] + a[2,1] + b[3,1]
    end
  end
  
  return c
end

def is_sorted(a)
  (0..a.size-2).each { |i|
    return false if a[i] > a[i+1]  
  }
  return true
end

[1,2,3,4,5].permutation.each { |p|
  p1 = Array.new(p)
  if !is_sorted(sort(p)) || sort(p).size != p.size
    puts "ERROR #{p1.to_s} --> #{sort(p1).to_s}"
  end
}

In lines 37, 39, 43 & 45, you are selecting 0 elements a at position 0. I think it's a mistake and should be a 1

In lines 37, 39, 43 & 45, you are selecting 0 elements a at position 0. I think it's a mistake and should be a 1

True enough. Had a silly bug in the test code, d'oh ... thanks! 👍