An efficient algorithm was given in . The algorithm will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching. Irving's algorithm has O(n2) complexity, provided suitable data structures are used to implement the necessary manipulation of the preference lists and identification of rotations.
