So I've run into a few occasions where I'd want to sort a list according to a criteria, then for all loosely sorted sublists (a sequence of equal elements), I'd want to sort those sublists according to another criteria. I previously did something like this (assuming there are
sorted(sorted(sorted...(sorted(lst, key = keys[m]), key = keys[m-1]), ..., key = keys), key = keys).
Generally, I had around two sorting criteria so it wasn't an issue. Working on a problem that required sorting according to 3 criteria led me to generalise my method, which led me to noticing that it had atrocious resource usage (best case time complexity is
s is the time complexity of
sorted(), and best case space complexity is
n is the length of the list). This prompted me to seek more efficient ways of doing this, and after some thought, discussion and feedback from others, here's what I have:
from collections import deque """ * Finds all sublists that have equal elements (according to a provided function) in a given sorted list. * Params: * `lst`: The sorted list to be searched. * `f`: The function that is used to compare the items in the list. * Return: * A list containing 2 tuples of the form `(start, stop)` where `start` and `stop` give the slice of equal values in the list. If no elements in the list are equal this is empty. """ def checkSort(lst, f = lambda x: x): #Finds all sublists that have equal elements in a given sorted list. i, slices, ln = 0, , len(lst) while i < ln-1: if f(lst[i]) == f(lst[i+1]): j = i+1 while f(lst[i]) == f(lst[j]): if j+1 == ln: break j += 1 slices.append((i, j)) #The slice can be directly accessed using `lst[tpl:tpl]` where `tpl` is the tuple denoting the slice. i = j continue #`i` should not be further increased. i += 1 #Increment `i` normally if `i+1` != `i`. return slices """ * Returns a sorted list whose elements are drawn from a given iterable, according to a list of provided keys. * It is equivalent to a lazily evaluated form of `sorted(lst, key = lambda x: (key1(x), key2(x), key3(x) [,..., keym(x)]))`. The lazy evaluation provides the same `O(s)` (where `s` is the time complexity of `sorted()`) best case as a simple `sorted()` with only one key. On the other hand, the best case of the above (due to its strict evaluation) is `O(m*s)` where `m` is the number of supplied keys. This function would be very useful in cases where some of the key functions are expensive to evaluate. The process can be described as: * Elements are ordered according to criterion 1. * Elements equal by criterion 1 are ordered according to criterion 2. * ... * ... * ... * Elements equal by criterion i are ordered according to criterion i+1. * ... * ... * ... * Elements equal by criterion n-1 are ordered according to criterion n. * This process is being referred to as "Chained Sort". * Algorithm for Chained Sort: * Step 1: lst := sorted(itr, keys[i]), ln := len(keys) * Step 2: i := i+1 * Step 3: If i < ln and some elements in the list are equal according to criterion i: * Step 4: while there exist elements equal according to criterion i: * Step 5: Find the slices of all elements equal according to criterion i. * Step 6: Sort those slices according to criterion i. * Step 7: i := i+1 * [End of Step 4 while loop.] * [End of Step 3 if block.] * Step 8: Return lst. * Params: * `itr`: The iterable to be sorted. * `keys`: A deque containing all the sorting keys, in the order in which they are to be evaluated. * Return: * `lst`: The sorted contents of `itr`, after applying the chained sort. """ def chainedSort(itr, keys = deque([lambda x: x])): lst = sorted(itr, key = keys.popleft()) check =  if not keys else checkSort(lst, keys.popleft()) while keys and check: k = keys.popleft() for tpl in check: #Sort all equal slices with the current key. i, j = tpl, tpl lst[i:j] = sorted(lst[i:j], key = k) if keys: k, tmp = keys.popleft(),  """ * We only need to check those slices of the list that were not strictly sorted under the previous key. Slices of the list that were strictly sorted under a previous key should not be sorted under the next key. As such, rather than iterating through the list every time to find the loosely sorted elements, we only need to search among the loosely sorted elements under the previous key, as the set of loosely sorted elements cannot increase upon successive sorts. """ for tpl in check: i, j = tpl, tpl tmp.extend(checkSort(lst[i:j], k)) check = tmp else: check =  return lst