There are two main ways to sort a linked list, the easiest to implement is the insertion sort, but because that is a N squared algorithm, it is not terribly efficient for large data sets.

However, by luck the Merge Sort lends itself well to linked lists. Merge sorting Linked lists is very fast and effecient, but memory intensive.

Here then is a linked list implementation of the Merge Sort.

This code will work as long as the linked list objects sorted (Called "Entry" in this code) are a singly linked list with a field called "next" in the object that points to the next element in the list. You pass the sort the first element of the list (its head) and the algorithm works well.

By changing only a couple of lines, this can also be a very effective Shuffling algorithym

  public static Entry merge_sort (Entry list1) {
        if (list1 == null || list1.next == null)
           return list1; // checks for empty or single list
        Entry list2 = split (list1);
        list1 = merge_sort (list1);
        list2 = merge_sort (list2);
        return merge (list1, list2);
  } // end merge_sort

  public static Entry split (Entry list1) {  // if possible, split the list into two lists, if not, return null;
        if (list1 == null || list1.next == null) return null;
        Entry list2 = list1.next;
        list1.next = list2.next;
        list2.next = split (list2.next);
        return list2;
  } // end split method

  public static Entry merge (Entry list1, Entry list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.word.compareToIgnoreCase(list2.word) < 0) {  // by changing this line to some sort of random function, this algorithm could shuffle as well as sort.
                list1.next = merge (list1.next, list2);
                return list1;
        } // end if
        else {
                list2.next = merge (list1, list2.next);
                return list2;
        } // end else
  } // end merge method

CCDS Sidebar