Sort operation

The List sort() function provides an efficient method for sorting a List in place, for example, L.sort(LessThan). sort() uses a mergesort algorithm, which is O(nlog n) in complexity. (See the examples in the section, ``Example'', for an insertion sort() operation with quadratic complexity.)

Because no total ordering or T::operator<() is assumed on T, the user must provide a function to do the comparison between elements of the List. This user-defined function has type int (*)(const T&,const T&) for sorting a List<T> and int (*)(const T*&,const T*&) for sorting a List_of_p<T>. All this really means is that the function, for example, LessThan(), has the following signature:

   int LessThan( const T&, const T& );    // for Lists

   int LessThan( const T*&, const T*& );  // for List_of_ps

   class Student {
      String name;
      String grade;
   public:
      Student(const String&,const String&);
      Student(const Student&);
      int operator==(const Student&);
      friend ostream& operator<<(ostream&,
          const Student&);
      friend int name_compare(const Student&,
          const Student&);
      friend int grade_compare(const Student&,
          const Student&);
   };
   

   int name_compare(const Student& s1,
     const Student& s2)
   {
      if(s1.name + s1.grade < s2.name + s2.grade)
          return 1;
      return 0;
   }
   

   int grade_compare(const Student& s1,
     const Student& s2)
   {
      if(s1.grade < s2.grade)
          return 1;
      return 0;
   } 

These comparison functions can now be used to sort a List of Foos two different ways in the following program:

   #include <Student.h>
   #include <List.h>
   #include <iostream.h>
   

   main()
   {
       Student s1("George","A");
       Student s2("Arthur","D");
       Student s3("Chester","C");
       Student s4("Willy","B");
       List<Student> Class(s1,s2,s3,s4);
       cout << Class << "\0;
       Class.sort(name_compare);
       cout << Class << "\0;
       Class.sort(grade_compare);
       cout << Class << "\0;
   }

would have the following output:

   ( George: A, Arthur: D, Chester: C, Willy: B )
   ( Arthur: D, Chester: C, George: A, Willy: B )
   ( George: A, Willy: B, Chester: C, Arthur: D ) 

The sort() operation does not preserve the position of any of the iterators (see the section, ``List iterators''. It is the responsibility of the user to reset the iterators after the sort() operation.