CODE IN JAVA

/** * Sort the cards using the given comparison, so that * after sorting for all cards c in the group that is not last * cmp.compare(c,c.next) is never positive. * This code must use insertion sort so that it is efficient * on (mostly) sorted lists. * @param cmp comparator to use for sorting. Must not be null. * The comparator should work correctly, or the final result is undefined. */ public void sort(Comparator cmp) { assert wellFormed() : "invariant false on entry to sort()"; for (Card c = dummy.next.next; c != dummy; ) { Card next = c.next; // the next card to insert Card prev = c.prev; // the card after which to insert c // TODO: Move prev back as necessary so that // it is the card that that c should go after: // (You will need to use the comparator.) if (c.prev != prev) { // if it's the same, the card doesn't move! // we have to swap, which has two steps: // (1) remove it from where it is: c.prev.next = c.next; c.next.prev = c.prev; // (2) stick in new location: c.prev = prev; c.next = prev.next; c.next.prev = c; c.prev.next = c; } c = next; } assert wellFormed() : "invariant false on exit to sort()"; }