Ruby实现2路插入排序；2路插入排序基于折半插入排序

two-way binary sort

#!/usr/bin/env ruby

def two_way_sort data
  first,final = 0,0
  temp = []
  temp[0] = data[0]
  result = []
  len = data.length

  for i in 1..(len-1)
    if data[i]>=temp[final]
      final +=1
      temp[final] = data[i]
    elsif data[i]<= temp[first]
      first = (first -1 + len)%len
      temp[first] = data[i]
    else
      if data[i]<temp[0]
	      low = first
        high = len -1
    	
	      while low <=high do
          m = (low + high)>>1
	        if data[i]>temp[m]
            low = m + 1
          else
            high = m -1
	        end
	      end
        
	      j = first - 1
        first -=1
	      while j < high do
	        temp[j] = temp[j+1]
	        j +=1
    	  end
	
	      temp[high] = data[i]
      else
        low =0
        high = final

        while low <=high do
          m =(low + high)>>1

          if data[i]>=temp[m]
            low = m + 1
          else
            high = m - 1
          end
        end

        j = final + 1
        final +=1

        while j > low do
          temp[j] = temp[j-1]
          j -=1
        end 

        temp[low] = data[i]
      end
    end 
    p temp 
  end

  i = 0
  for j in first..(len - 1)
    result[i] = temp[j]
    i +=1
  end

  for j in 0..final
    result[i] = temp[j]
    i +=1
  end

  return result
end


data = [4,1,5,6,7,2,9,3,8].shuffle

p data

result = two_way_sort data

p result