Lack of stable sort in Python's priority queue

I wrote earlier about modeling Python's priority queue using the "list" data type, in order to find a rumored source of error in implementing the Dijkstra shortest-path algorithm.

I see now that there is an important feature, possible in the list model but apparently not in the priority queue: stable sorting. I've altered my queue_test code to illustrate this difference. I am dealing here with v. 2.6 of Python.

When a list of lists is sorted under normal conditions, all items of the sub-lists take part in the sorting: their first item is sorted, then their second item, then their third, and so on. The result looks like this:

[6, 17, 18, 16]
[6, 17, 18, 17]
[6, 17, 19, 6]
[6, 17, 20, 7]
[6, 17, 20, 16]
[6, 18, 1, 5]
[6, 18, 1, 13]
[6, 18, 2, 2]
[6, 18, 2, 5]
[6, 18, 2, 12]
[6, 18, 3, 2]
[6, 18, 3, 6]
[6, 18, 3, 6]
[6, 18, 4, 19]
[6, 18, 4, 20]

All these lists begin with 6, but we cannot tell anything about their original order relative to each other. Those whose second element is 17 all come before those whose second element is 18. Among those beginning [6, 18], those whose third element is 1 all come before those whose third element is 2. And so forth. The sorting process is carried out on all elements, leaving no trace of the original order of the lists.

In a stable sort, however, only some specified item is sorted, and the other items are not examined, so a remnant of the earlier order persists in the sorted result. The result might look like this:

[6, 17, 18, 16]
[6, 9, 20, 4]
[6, 9, 19, 6]
[6, 20, 18, 11]
[6, 20, 6, 12]
[6, 19, 1, 12]
[6, 17, 4, 8]
[6, 12, 9, 20]

You can see that [6, 17, 18, 16] "ought" to be placed after [6, 9, 20, 4], and so forth, but stable sorting has left them out of order, reflecting their original relative position.

Stable sort in Python 2.6 is achieved by use of a key as an argument of the sort() method, and can be refined by use of the itemgetter() method of the operator module. But Python's priority queue does not seem able to sort by a key or to sort stably. For an illustration, see the current version of my queue_test code, online at https://bitbucket.org/dpb/queue_test.

[end]