Alternating sort order within a sorted group

Question

When sorting by multiple keys, I need the second key to alternate between standard and reverse sorting. This is to minimize the change in the second key. For example, if I have a list of dictionaries, I want the first sort (group key) to be sorted and then the second sort (sort key) to alternate. This should produce a sort like this:

[{'group': 'a', 'sort': 1},
 {'group': 'a', 'sort': 2},
 {'group': 'a', 'sort': 2},
 {'group': 'b', 'sort': 2},
 {'group': 'b', 'sort': 1},
 {'group': 'b', 'sort': 1},
 {'group': 'c', 'sort': 1},
 {'group': 'c', 'sort': 1},
 {'group': 'c', 'sort': 2}]

That limits the change in the field called "sort" as it alternates each time as the "group" changes.

I have looked around and did not see a standard way to accomplish this without rolling my own. I think the code is fairly straight forward but curious if I might be missing something or an easier/faster way.

Any comments would be appreciated.

#!/usr/bin/env python3
""" Misc sort routines """
from operator import itemgetter
import pprint


def alternate_sort(data, group_key, sort_key,
        group_reverse=False, sort_reverse=False):
    """ Sort data within groups while alternating asc/desc on sort key. """
    partitions = []     # Tuples of start/end indexes per group
    last_key = None     # Remember when groups change
    group_start = 0     # Remember start index of group
    final_sort = []     # The final sorted listing

    # Make sure the data is sorted by group
    data = sorted(data, key=itemgetter(group_key), reverse=group_reverse)

    # Gather the group partitions
    for i, g in enumerate(data):

        # When the group changes
        if last_key != g[group_key]:

            # End the previous group partition if there is one
            if i > 0:
                partitions.append((group_start, i))

            # Start a new group partition
            group_start = i
            last_key = g[group_key]

    # Close the last group partition
    partitions.append((group_start, len(data)))

    # Go through the partitions, alternate the sort each time using sort key.
    for i, p in enumerate(partitions):
        part = data[p[0]: p[1]]
        if i % 2 == 0:
            final_sort += sorted(
                    part, key=itemgetter(sort_key), reverse=sort_reverse)
        else:
            final_sort += sorted(
                    part, key=itemgetter(sort_key), reverse=not sort_reverse)

    return final_sort


if __name__ == "__main__":
    unsorted_data = [
            {"group": "a", "sort" : 1},
            {"group": "a", "sort" : 2},
            {"group": "b", "sort" : 2},
            {"group": "b", "sort" : 1},
            {"group": "c", "sort" : 1},
            {"group": "a", "sort" : 2},
            {"group": "c", "sort" : 2},
            {"group": "b", "sort" : 1},
            {"group": "c", "sort" : 1}
    ]

    sorted_data = alternate_sort(unsorted_data, "group", "sort",
            group_reverse=True, sort_reverse=True)
    pprint.pprint(sorted_data)

    sorted_data = alternate_sort(unsorted_data, "group", "sort")
    pprint.pprint(sorted_data)

Answer 1

1. Quick review

1. This function returns a new list, like the built-in sorted. It does not update data in place, like the sort method on lists. So a name containing "sorted" would give a better hint at its behaviour.

2. The docstring is not detailed enough to explain how to call the function. What arguments do I pass for group_key and sort_key? What happens if I pass True for group_reverse or sort_reverse?

3. The function calls operator.itemgetter to make key functions. But this means that the function will only work when the keys are dictionary or sequence values. If you want to use object properties as keys, you're out of luck (that would need operator.attrgetter). And if you want to compute something more complicated by passing in your own function, that's no good either.

   I would recommend accepting any function for group_key and sort_key and letting the caller use operator.itemgetter if that's what they need. This makes the function behave more like the built-in sorted and similar functions that take key arguments.

4. Extend a list using the extend method, which updates the list in-place. If you use augmented assignment +=, Python may have to create a new list and copy all the elements across.

2. Rewrite

The algorithm you've chosen is:

1. Sort data by the group key.

2. Iterate over the data, collecting the groups.

3. Iterate over the groups, sorting each one.

Steps 2 and 3 can be combined into one iteration using itertools.groupby. The alternation between ascending and descending can be implemented using itertools.cycle. These two iterations can be combined using zip, like this:

from itertools import cycle, groupby

def sorted_alternately(data, group_key, sort_key,
                       group_reverse=False, sort_reverse=False):
    """Sort data on group_key (in reverse order if group_reverse=True) but
    within each group of items, alternately sort in ascending and
    descending order on sort_key (in descending and ascending order in
    sort_reverse=True).

    >>> from itertools import product
    >>> from operator import itemgetter as get
    >>> sorted_alternately(product(range(3), repeat=2), get(0), get(1))
    [(0, 0), (0, 1), (0, 2), (1, 2), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2)]

    """
    data = sorted(data, key=group_key, reverse=group_reverse)
    groups = groupby(data, key=group_key)
    reverses = cycle((sort_reverse, not sort_reverse))
    result = []
    for (_, group), reverse in zip(groups, reverses):
        result.extend(sorted(group, key=sort_key, reverse=reverse))
    return result