If both sides on the input come in sorted, couldn't we merge the two sides and maintain sortedness in linear time? (Actually, I think unix's `sort` command has this functionality)