Ruby 实现折半插入排序

Binary Insertion Sort

#!/usr/bin/env ruby

def b_insertion_sort(data)

  stop = data.length - 1

  (1..stop).each do |i| 
    tmp = data[i]
    low = 0
    high = i- 1
    
    while low <= high do
      mid = (low + high) >> 1
      if tmp < data[mid]
        high = mid - 1;
      else
        low = mid + 1
      end
    end
    
    j = i -1
    while j>=low do
      data[j+1] = data[j]
      j -=1
    end

    data[low] = tmp

  end

 return data
  
end

data = [1,2,3,4,5,6,7,8,9,12,34].shuffle
p "Before Binary Sort:"
p data
result = b_insertion_sort(data)
p "After Binary Sort:"
p result