Fun! Here's Ruby:

  def top_four_ints_from(input_list)                                                    
    working_set = []

    input_list.each do |n|                                                    
      working_set.push(n)
      working_set.sort!.shift while working_set.count > 4
    end                                                 
                                                                                 
    working_set                                                               
  end

I'm pretty sure that's O(n). Constant time to insert any one value to the working set, Roughly n sorts performed but since each individual sort covers at most five elements we're still at (5 lg 5) * n -> O(n).