Sorting a nested OrderedDict by key, recursively

Question

Say orig is an OrderedDict which contains normal string:string key value pairs, but sometimes the value could be another, nested OrderedDict.

I want to sort orig by key, alphabetically (ascending), and do it recursively.

Rules:

• Assume key strings are unpredictable
• Assume nesting can take place infinitely, e.g. level 1-50 all have both strings, OrderedDicts, etc as values.

Need an assist with the sorted algorithm:

import string
from random import choice


orig = OrderedDict((
    ('a', choice(string.digits)),
    ('b', choice(string.digits)),
    ('c', choice(string.digits)),
    ('special', OrderedDict((
        ('a', choice(string.digits)),
        ('b', choice(string.digits)),
        ('c', choice(string.digits)),
    )))
))

sorted_copy = OrderedDict(sorted(orig.iteritems(), ...))

self.assertEqual(orig, sorted_copy)

Answer 1

EDIT: for python 3.6+, @pelson's answer is better

something like:

def sortOD(od):
    res = OrderedDict()
    for k, v in sorted(od.items()):
        if isinstance(v, dict):
            res[k] = sortOD(v)
        else:
            res[k] = v
    return res

Answer 2

@acushner's solution can now be simplified in python3.6+ as dictionaries now preserve their insertion order.

Given we can now use the standard dictionary, the code now looks like:

def order_dict(dictionary):
    result = {}
    for k, v in sorted(dictionary.items()):
        if isinstance(v, dict):
            result[k] = order_dict(v)
        else:
            result[k] = v
    return result

Because we can use standard dictionaries, we can also use standard dictionary comprehensions, so the code boils down to:

def order_dict(dictionary):
    return {k: order_dict(v) if isinstance(v, dict) else v
            for k, v in sorted(dictionary.items())}

See also https://mail.python.org/pipermail/python-dev/2016-September/146327.html for detail on python's ordered dictionary implementation. Also, the pronouncement that this will be a language feature as of python 3.7: https://mail.python.org/pipermail/python-dev/2017-December/151283.html