Skip to main content

Partially ordered sort

Project description

An algorithm to sort a collection by a sequence of comparators.


A comparator takes two elements a and b and returns

0 - if they are equal a positive number if a > b a negative number if a < b

For example the natural comparator on the integers is

def small_first(a, b):

return a - b

The Python sorted function takes a comparator function as a keyword input

>>> sorted([1, 5, 2, 4, 3], cmp=small_first)
[1, 2, 3, 4, 5]

We may choose to sort by different criteria. For example we might choose to prefer even numbers

def evens_first(a, b):

return a%2 - b%2

>>> sorted([1, 5, 2, 4, 3], cmp=evens_first)
[4, 2, 5, 1, 3]

Note in the example above that all of even numbers precede all of the odd numbers; evens_first is satisfied. Also note that there are several possible solutions. In this case there are 12 possible solutions that all satisfy the comparator function. sorted returns one at random.


To obtain the solution [2, 4, 1, 3, 5] where numbers are sorted first by evenness and then by magnitude we can use the function posort.

The posort function attempts to satisfy a sequence of comparator functions of decreasing precedence.

>>> posort([1, 5, 2, 4, 3], evens_first, small_first)
[2, 4, 1, 3, 5]

The rule for even numbers dominates the rule for small numbers. Any number of comparator functions can be specified.

Equivalent structures

A comparator function completely specifies a [partial order](

A comparator function can describe any [directed acyclic graph (DAG)](


[Matthew Rocklin](


New BSD license. See LICENSE.txt


This idea was originally developed for the [Theano project](

Project details

Release history Release notifications | RSS feed

This version


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

posort-0.1.tar.gz (3.1 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page