ソート

sorts.rb

def merge(left, right)
  merged = []
  first_index = 0
  second_index = 0
  while first_index < left.length || second_index < right.length 
    if first_index == left.length
      merged << right[second_index]
      second_index += 1
      next
    end
    
    if second_index == right.length
      merged << left[first_index]
      first_index += 1
      next
    end

    if left[first_index] > right[second_index]
      merged << right[second_index]
      second_index += 1
    else
      merged << left[first_index]
      first_index += 1
    end
  end
  return merged
end
def merge_sort(ary)
  if ary.length <= 1  
    return ary
  end
  middle = ary.length/2
  first = ary.slice(0..(middle-1))
  second = ary.slice(middle..(ary.length-1))
  sorted_first = merge_sort(first)
  sorted_second = merge_sort(second)
  return merge(sorted_first, sorted_second)
end
def make_heap(ary, stand, bottom)
  child_left = 2*stand+1
  child_right = 2*stand+2
  max_index = stand
  if child_left < bottom
    max_index = child_left if ary[max_index] < ary[child_left] 
    max_index = child_right if ary[max_index] < ary[child_right] 
  elsif child_left == stand
    max_index = child_left if ary[max_index] < ary[child_left] 
  end
  if max_index != stand
    tmp = ary[stand]
    ary[stand] = ary[max_index]
    ary[max_index] = tmp
    make_heap(ary, max_index, bottom)
  end
end
def heap_sort(ary)
  ((ary.length-1)/2).downto(0) do |i|
    make_heap(ary, i, ary.length-1)
  end
  (ary.length-1).downto(1) do |i|
    tmp = ary[0]
    ary[0] = ary[i]
    ary[i] = tmp
    make_heap(ary, 0, i-1)
  end
end
ary = [2,6,4,3,6,7,23]
heap_sort(ary)
p ary