Given a list of n people, suppose that each person has a "friendliness" rating. This rating is an integer value somewhere between 0 and n-1, where "0" means they are always unfriendly to every other person they meet, and "n-1" means they are always friendly with all of the other n-1 people in the population. So, for example, if Susan is friendly towards Bob, James, and Erica, but no one else, she would have a friendliness rating of "3". In other words, a person's "friendliness" score is a count of the number of people in the population who the person is friendly towards.

We do not have direct access to these "friendliness" values. We cannot call a function such as p1.getFriendliness() to look up how friendly a person is. Similarly, we do not have access to a function which will list out which people an individual is friendly towards ( p1.getFriends() ). We cannot even check to see if a person is friendly towards another person directly (p1.isFriendlyTowards( p2) ), because a person would not actually admit that they are "not friendly" towards someone else (that would make them the villain)!

The only thing that we can do to observe friendliness behavior through the function meetup( p1, p2), which takes input of two "people" p1 and p2 and returns a Boolean value.

When two people meetup, they either get along or they do not based upon whether they are friendly towards one-another. Unfortunately, one person being friendly is not sufficient for two people to get along--both need to be friendly towards each other. So, when two people meetup, there are 2 possible outcomes:

1) They get along (both are friendly to each other), IE: meetup(p1,p2) returns True

2) They do not get along (one or both are unfriendly), IE: meetup(p1,p2) returns False

Assume that the meetup function runs in time O(1) and uses O(1) space. GIVEN a list of n people, sort the people in ascending order by friendliness ratings. And now consider a special case of the problem: Each person in the population either has a friendliness rating of 0 (not friendly to anyone) or n-1 (friendly to everyone). Design an algorithm which will correctly sort a special-case list of n people in ascending order by friendliness ratings (minimum 0, maximum n-1). The resulting list will have all of the 0-friendliness people first followed by all of the people with a friendliness of n-1. Given the limitations of the meetup function, it is impossible to distinguish between a group of people with only 1 friendly person and a group of people with 0 friendly people, even in this special case. Your algorithm will not need to work for these two cases.

Note that a person cannot have two different friendliness scores; once we know their score, we can potentially use that information to our advantage to improve the efficiency of the algorithm. Key to designing this algorithm is keeping in mind the following:

Observation 1) When meetup(p1,p2) returns true, this means (for the special case) than both p1 and p2 have friendliness score of n-1

Observation 2) When meetup(p1,p2) returns false, this means (for the special case) that at least one of the two (p1 or p2, possibly both) has a friendliness score of 0

The algorithm should be pseudocode