Java LinkedList sort: stable order needs temporary array work

The Java 8 program below compiles without external libraries; its output is checked against a real run.

State the tie rule

Three receipts arrive in order R-11, R-12, R-13. Sorting by priority moves R-12 first while R-11 remains before R-13 because both have priority two. That stable tie behavior is useful only if encounter order itself is meaningful and retained through earlier processing.

A comparator must provide a consistent ordering. Subtracting large integer priorities to compare them can overflow; Comparator.comparingInt avoids that arithmetic. Comparator contracts covers transitivity and equality issues.

Do not assume pointer relinking removes memory cost

The Java 8 List default sort obtains an array, sorts it, then writes values back through a list iterator. LinkedList nodes remain, but the algorithm still needs array storage. For repeated indexed queries after sorting, an array-backed representation may serve the workload better.

Working program

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
public class ReceiptPrioritySort {
    static final class Receipt {
        final String id; final int priority;
        Receipt(String id, int priority) { this.id = id; this.priority = priority; }
        public String toString() { return id; }
    }
    public static void main(String[] args) {
        LinkedList<Receipt> receipts = new LinkedList<>(Arrays.asList(
            new Receipt("R-11", 2), new Receipt("R-12", 1), new Receipt("R-13", 2)));
        receipts.sort(Comparator.comparingInt(receipt -> receipt.priority));
        System.out.println(receipts);
    }
}

Output

[R-12, R-11, R-13]

Costs and boundaries

General comparison sorting is O(n log n) in the worst case. The Java 8 default List.sort uses an array of n references plus sorting workspace; no claim of in-place constant memory is made.

Common Mistakes

• Do not use subtraction as a general integer comparator.
• Do not assume stable order can repair an earlier unordered source.
• Do not assume a linked structure removes the sort's array allocation.

Read next

Java LinkedList: operations, internals and failure cases, Java comparators: tie-breakers, overflow and sorted-key identity, Java ArrayList and indexed access.

Continue with owned-node algorithms

Continue with Stable merge sort for a singly linked chain in Java.