Results

Solution1 valid: true
Solution1:   2.280000   0.000000   2.280000 (  2.275380)
Solution2 valid: true
solution2:   1.220000   0.000000   1.220000 (  1.222917)
Solution3 valid: true
solution3:   1.470000   0.010000   1.480000 (  1.481871)
Solution4 valid: true
solution4:   2.080000   0.000000   2.080000 (  2.075977)
 => [  
2.280000   0.000000   2.280000 (  2.275380),
1.220000   0.000000   1.220000 (  1.222917),
1.470000   0.010000   1.480000 (  1.481871),
2.080000   0.000000   2.080000 (  2.075977)
]

Sort and Group Benchmark

require 'benchmark'

test_array = [
  {"timestamp"=>1347119549, "category"=>nil},
  {"timestamp"=>1347119547, "category"=>"Monkeys"},
  {"timestamp"=>1347119543, "category"=>nil},
  {"timestamp"=>1347119542, "category"=>"Monkeys"},
  {"timestamp"=>1347119548, "category"=>"Dog"},
  {"timestamp"=>1347119544, "category"=>"Dog"}
 ].freeze

def solution1(orig)
  grouped = orig.group_by { |x| x["category"] ?  x["category"] : Object.new  }

  # Sort the siblings within the groups (note negation causes reverse order)
  grouped.values.each { |siblings| siblings.sort_by! { |a| -a["timestamp"] } }

  # Sort the list by first (i.e. "best" sort order) timestamp in each group 
  sorted_groups = grouped.sort_by { |group_id,siblings| -siblings.first["timestamp"] }

  # Remove group ids and flatten the list:
  sorted_groups.map { |group_id,siblings| siblings }.flatten
end

def solution2(arr)
  sorted = arr.sort_by { |elem| 0 - elem['timestamp'] }
  groups = sorted.group_by { |elem| elem['category'] or Object.new }
  groups.values.flatten
end

def solution3(a)
  groups = a.sort_by {|h| -h['timestamp']}.group_by {|h| h['category']}
  sorted = (groups.delete(nil) || []) + groups.values
  sorted.sort_by{|i| i.is_a?(Hash) ? -i['timestamp'] : -i.first['timestamp']}.flatten
end

def solution4(ar)
  ar.group_by{|h| h['category'] ? h['category'] : h['timestamp']}.
  map{|k,v| v.sort_by{|h| -h['timestamp']}}.
  sort_by{|a| -a[0]['timestamp']}.flatten
end

n = 100000
Benchmark.bm do |benchmark|
  puts solution1(test_array)
  benchmark.report('solution1: ') { n.times { solution1(test_array) } }

  puts solution2(test_array)
  benchmark.report('solution2: ') { n.times { solution2(test_array) } }

  puts solution3(test_array)
  benchmark.report('solution3: ') { n.times { solution3(test_array) } }

  puts solution4(test_array)
  benchmark.report('solution4: ') { n.times { solution4(test_array) } }
end