ヒープソート

まず、失敗作を

def heap(array,n)
  return if n<=0
  parent = (n - 1) / 2 # 親の位置
  if array[n] > array[parent]
    array[n], array[parent] = array[parent], array[n]
  end
  heap(array,parent)
end

def heap_sort(array,sorted)
  return sorted << array.shift if array.length == 1

  (array.size-1).downto(1) do |n|
    heap(array,n)
  end

  sorted << array.shift
  array.unshift(array.pop)
  heap_sort(array,sorted)
end

ソート済み配列を作ってそこにいれる。
コードはとてもわかり易いが無駄な計算が多い。
ということで改良版(ついでにArrayクラスのメソッドにした）

class Array
  def heap_sort!
    build_heap

    (size - 1).downto(1) do |i|
      self[0], self[i] = self[i], self[0] #最大値[0]を一番後ろ[i]に詰めていく
      heapify(0, i)
    end
  end

  def build_heap
    ((size - 1) / 2).downto(0) do |i|
      heapify(i)
    end
  end

  def heapify(index, heap_size = size) #current_indexとソート済みでない配列の数
    left = index * 2 + 1
    right = index * 2 + 2

    largest = index
    largest = left  if left  < heap_size && self[left]  > self[largest]
    largest = right if right < heap_size && self[right] > self[largest]

    if largest != index
      self[largest], self[index] = self[index], self[largest] #大きいのを上へ
      heapify(largest, heap_size) #下へ行ったほうがどこまで下がるか
    end

  end
end

失敗作との最大の違い「親から子」を求めている点だと思う。
若干わかりにくくはなるけど、heapを作るとこで無駄な計算が減ってる。

参考にしたリンク
[ruby] ヒープソート実装 | このコードわからん