 Solution

Repeatedly detach the minimum and append that very node to a separate output chain:

function Sort(xs: List): List
    allocate dummy headers remaining and output
    remaining.next := xs
    output.next := nil
    tail := output
    while remaining.next != nil do
        p := DelMin(remaining)
        tail.next := p
        tail := p
    return output.next

The loop invariant says that the output and remaining chains contain disjoint subsets of the original data nodes, together containing every original node exactly once. The output is nondecreasing, its final key is no larger than any remaining key, and tail points to its final node, or to the dummy header when empty. Its outgoing link is nil because DelMin detaches the returned node. Appending the remaining minimum preserves all these properties; the remaining node count decreases by one.

At exit the output is the complete sorted bag. This iterative selection sort preserves duplicate occurrences and, with first-minimum tie handling, their original relative order. It uses $\Theta (N^2)$ time and $O(1)$ auxiliary nodes. “Increasing” here means nondecreasing when equal keys occur.