sort.rb

def min(nums)
  min = nums[0]
  min_i = 0
  nums.each_with_index do |n, i|
    if n < min
      min = n
      min_i = i
    end
  end
  [min, min_i]
end

def selection(nums)
  i = 0
  until i == nums.length
    min_n, min_i = min(nums[i..-1])
    nums[i], nums[min_i + i] = nums[min_i + i], nums[i]
    i += 1
  end
  nums
end

def insertion(nums)
  i = 1
  until i == nums.length
    j = i - 1
    while j >= 0 and nums[j] > nums[j + 1]
      nums[j + 1], nums[j] = nums[j], nums[j + 1]
      j -= 1
    end
    i += 1
  end
  nums
end

def merge(nums)
  m = (nums.length / 2).floor
  if m == 0
    return [nums[0]]
  end
  nums[0...m] = merge(nums[0...m])
  nums[m..-1] = merge(nums[m..-1])
  arr = Array.new(nums.length)
  i = 0
  j = m
  k = 0
  until k == nums.length
    if i == m or (j != nums.length and nums[j] < nums[i])
      arr[k] = nums[j]
      j += 1
    else
      arr[k] = nums[i]
      i += 1
    end
    k += 1
  end
  arr
end

# array = [0, 11, -5, 2, 7, 10, -2]
# array = Array.new(10) { rand(-10..10) }
# array = Array.new(rand(5..10000)) { rand(-1000..1000) }
array = Array.new(ARGV[0].to_i) { rand(-1000..1000) }
# array = (0...(ARGV[0].to_i)).to_a.reverse

# puts array.inspect

puts "n = #{array.length}"

sorted = selection(array.dup)

dup = array.dup
start = Time.now
puts "selection: #{Time.now - start}s" if selection(dup) == sorted

dup = array.dup
start = Time.now
puts "insertion: #{Time.now - start}s" if insertion(dup) == sorted

dup = array.dup
start = Time.now
puts "merge: #{Time.now - start}s" if merge(dup) == sorted