Ruby的归并排序

ruby 代码 [sort.rb]

#!/usr/bin/env ruby
class Sort
  def putList(l)
    a = []
    a = l
    b = "["
    a.each do |aa|
      b += (aa.to_s + ",")
    end
    b += "]"
    b.gsub!(/,\]/,']')
    puts b
  end
end

ruby 代码 [MergerSort.rb]

#!/usr/bin/env ruby
require 'Sort'

class MergerSort < Sort
  @list = []
  def sort(l)
    @list = l
    mergeSort(@list,0,@list.length - 1)
    putList @list
  end
  def merge(a,p,q,r)
    list_L = a[p,q-p+1]
    list_R = a[q+1,r-q+1]

    list_L[q-p+1] = "eof"
    list_R[r-q] = "eof"

    i = 0
    j = 0

    until i + j > r-p
      if list_L[i] != "eof" && ( list_R[j] == "eof" || list_L[i] < list_R[j])
        a[p+i+j] = list_L[i]
        i += 1
      elsif list_R[j] != "eof"
        a[p+i+j] = list_R[j]
        j += 1
      end
    end
  end

  def mergeSort(a,p,r)
    if p < r
      q = (p + r) / 2
      mergeSort(a,p,q)
      mergeSort(a,q+1,r)
      merge(a,p,q,r)
    end
  end
end

ms = MergerSort.new
#a = [2,4,3,1,2.5,0,6,100,24,64,18,72,100,88,99,88]
a = []
1000.times do
  a << rand(1000)
end
t1 = Time.new
ms.sort(a)
t2 = Time.new
puts "%.6f" % (t2.to_f - t1.to_f)