Insertion sorting an endogenous list of cards

Question

I have a method that sorts a hand of cards in an endogenous doubly linked list.

public void sort(Comparator<Card> cmp) {
// source code that I am adapting my code from
 //          for (int i=0; i < a.length; i++) {
 //                 /* Insert a[i] into the sorted sublist */
//                  Object v = a[i];
//                  int j;
//                  for (j = i - 1; j >= 0; j--) {
//                      if (((Comparable)a[j]).compareTo(v) <= 0) break;
//                      a[j + 1] = a[j];
//                  }
//                  a[j + 1] = v;
//              }

        for(Card f = first; f!=null; f = f.next){
            Card insert = f;
            for(Card l = last; l!=null || l!= f; l = l.prev)
            {
                Card compare = l;
                if(cmp.compare(compare, insert) <=0) 

                    remove(insert);
                    this.add(insert);
                    break;

            }
        }


        // Make sure to test invariant before and after
        // You may find it helpful to use "remove" (but watch about size!)
    }

When I run this code it is not sorting correctly. Any pointers?

Answer 1

At a quick glance, I see three bugs. There may be more.

• Instead of l != null || l != f, I'm pretty sure you want && - the condition as you've written it is always true.
• You should use {} to delimit the "true" branch of your if. Currently, this.add(insert); and break; will run whether the if condition is true or false - and your indentation suggests that this isn't what you're expecting.
• In this.add(insert), you're not specifying where in the list to add the new node. I would expect to see something that specifies you'll be adding it at the position indicated by l.