LinkedList/merge_sort_linked_list library

� Sort Linked List (Merge Sort) — scalable, stable, generic

Performs a stable merge sort on a singly linked list and returns the sorted head. The implementation splits lists using the tortoise-hare technique and merges by comparing values using Comparable, making it generic and safe for production use.

Contract:

  • Inputs: head (nullable linked list head) with T extends Comparable.
  • Output: head of the sorted list (nullable). Sort is stable (preserves order for equal keys).
  • Error modes: none; if values do not implement Comparable, compilation fails.

Complexity: Time O(n log n), Space O(log n) due to recursion depth.

Example:

final head = LinkedListNode.fromList([4,2,1,3]);
final sorted = mergeSortLinkedList(head);
// sorted: [1,2,3,4]

Functions

mergeSortLinkedList<T extends Comparable>(LinkedListNode<T>? head) → LinkedListNode<T>?