http://stackoverflow.com/questions/4686823/given-2-sorted-arrays-of-integers-find-the-nth-largest-number-in-sublinear-time

nth_largest.rb

#!/usr/bin/env ruby
# see http://timeless.judofyr.net/tailin-ruby for what the define_singleton_method's are about

define_singleton_method(:find_nth_largest_tco) do |a, b, n, low, high|
  if (high < low)
    return nil
  end

  mid = low + (high - low) / 2
  k = mid + binary_search(b, a[mid]) + 1

  if k < n
    low = mid + 1
    redo
  elsif k > n
    high = mid - 1
    redo
  else
    return a[mid]
  end
end

def find_nth_largest a, b, n
  if a.length + b.length < n
    return nil
  end

  in_a = find_nth_largest_tco(a, b, n, 0, [n, a.length - 1].min)
  if in_a
    return in_a
  end

  p
  in_b = find_nth_largest_tco(b, a, n, 0, [n, b.length - 1].min)
  if in_b
    return in_b
  end
end

def binary_search list, value
  binary_search_tco(list, value, 0, list.length - 1)
end

# algorithm is based off the tail recursive example on wikipedia
define_singleton_method(:binary_search_tco) do |list, value, low, high|
  if (high < low)
    return low
  end

  mid = low + (high - low) / 2

  if list[mid] > value
    high = mid - 1
    redo
  elsif list[mid] < value
    low = mid + 1
    redo
  else
    return mid
  end
end

if $0 == __FILE__
  # snippets.dzone.com/posts/show/2368
  class Numeric
    def ordinal
      to_s + ([[nil, 'st', 'nd','rd'],[]][self / 10 == 1 && 1 || 0][self % 10] || 'th')
    end
  end

  (50..55).each do |i|
    list = []
    current = 0
    i.times { list << (current += (rand(5) + 1)) }
  
    list.shuffle!
  
    a = []
    b = []
    list.each_index { |num| (num % 2 == 0) ? a << list[num] : b << list[num] }
    a.sort!
    b.sort!
  
    n = rand(i) + 1
  
    puts "Using a: #{a}"
    puts "      b: #{b}"
    puts "the #{n.ordinal} largest number is #{find_nth_largest(a, b, n)}"
    puts
  end
end

test_order.rb

#!/usr/bin/env ruby

require_relative './nth_largest'

if $0 == __FILE__
  times = []
  [1e4, 1e5, 1e6, 1e7, 1e8].map {|a| [1, 1.2, 1.5, 1.8, 2.2, 2.7, 3.3, 3.9, 4.7, 5.6, 6.8, 8.2].map { |b| (a * b).to_i }}.flatten.each do |i|
    p i
    list = []
    current = 0
    i.times { list << (current += (rand(5) + 1)) }
  
    list.shuffle!
  
    a = []
    b = []
    list.each_index { |num| (num % 2 == 0) ? a << list[num] : b << list[num] }
    a.sort!
    b.sort!
    
    n = rand(i) + 1
    
    start = Time.now
    find_nth_largest(a, b, n)
    end_time = Time.now
    
    times << { :i => i, :time => end_time - start }
  end

  File.open('output', 'w') do |file|
    file << ['i', 'time'].join("\t") << "\n"
    times.each do |time|
      file << [time[:i], time[:time]].join("\t") << "\n"
    end
  end
end