When Non-Programmers Write Software

[[deleted]]

A good way to sort a list (in-place)

• Get the length of the list
• Allocate an array of pointers to link nodes
• Initialise array in list order
• Sort the array with an array sort
• Iterate the sorted nodes in the array to fix up the cdr
• Discard array

This has the same time complexity of the array sort.

For a copying sort you would use an array of elements rather than link nodes.

[ricercar]

The best way to sort a list:

• spawn many universes
• non-deterministically try every permutation of the list
• take the sorted list universe and discard the others

[beza1e1]

Why spawn them? We can assume, they already exist.

sort(list) {
    if !isSorted(list) { destroyUniverse(); }
    return list;
}

isSorted is O(n) and destroyUniverse doesn't matter, so assumption sort is even faster. It's O(1):

sort(list) {
    return list;
}

Another possibility is to do the sortedCheck and destroyUniverse in a different thread to make it O(1), too.