University of Arizona, Department of Computer Science

CSc 120: Sorting Linked Lists

We will use an intuitively simple algorithm to sort linked lists. The essential idea is the following. Given a linked list to_be_sorted to sort, the algorithm repeatedly moves nodes from the original list to_be_sorted to a new list sorted, maintaining the condition that sorted is always kept in sorted order (i.e., for the purposes of this assignment, in descending order by the _value attribute).

Data structures

The algorithm has a linked list, sorted, which contains all of the nodes that have been sorted so far.

Initially, sorted is empty (i.e., sorted._head has the value None). Each iteration of the algorithm (step 2 below) adds a node to this linked list. The algorithm maintains the invariant that this list is always kept in sorted order.

Algorithm

The algorithm repeatedly performs the following steps:

  1. Remove a node, call it curr_element, from the head of to_be_sorted.

  2. Iterate down the list sorted to find the position where curr_element should be inserted such that, after curr_element has been inserted, sorted remains in sorted order.

  3. Insert curr_element at that position in sorted. This results in one more element being placed in sorted order in the sorted list.

The iteration stops when all elements have been moved from to_be_sorted to sorted. At that point, to_be_sorted will have the value None and sorted will have all of the nodes in sorted order. The algorithm then copies the list sorted to the head of to_be_sorted.

The key step in the algorithm above is step 2. The logic for this step is as follows. Here, we follow the requirement for this assignment that the list should be sorted in descending order. We say that an element A is "smaller than" an element B if A's _value attribute is less than B's _value attribute.

  1. If sorted is empty: add curr_element to the head of sorted.

  2. Otherwise, if the first element of sorted is smaller than curr_element: add curr_element at the head of sorted (so curr_element becomes the new first element).

  3. Otherwise, iterate down sorted to find an element E satisfying the following:

    1. E ≥ curr_element; and
    2. either E._next < curr_element, or E._next is None.

      (One way to do this uses two loops one after another: first, iterate down sorted to find the first node whose count is smaller than curr_element, call this node E1; second, iterate down sorted again to find the node E just before E1.)

    Insert curr_element immediately after E.

Example

Suppose that, initially, the list to_be_sorted is the following:

s0.png

Iteration 1

The first iteration of the algorithm moves the first element from to_be_sorted for insertion into sorted:

s1.png

Since sorted is empty (Item a in the algorithm above), curr_element is added to it as its only element:

s2.png

Note that this preserves the invariant that sorted is in sorted order.

Iteration 2

The algorithm again moves the (current) first element from to_be_sorted:

s3.png

Since this element is bigger than the first element of sorted (Item b in the algorithm above) it is inserted at the head of sorted:

s4.png

Note that, again, this preserves the invariant that sorted is in sorted order.

Iteration 3

The algorithm once again moves the (current) first element from to_be_sorted:

s5.png

Since this element is smaller than the first element of sorted (Item c in the algorithm above), the algorithm iterates down sorted to find the position where it should be inserted. In this case, item c.ii of the algorithm applies, with E._next == None; i.e., curr_element is inserted at the end of sorted:

s6.png

Note that, again, this preserves the invariant that sorted is in sorted order.

This process is repeated with the remaining elements of the linked list to_be_sorted.