from typing import Union
import copy
import collections


def dls_sort(orig: Union[dict, list, set]) -> Union[dict, list]:
    """
    Given a nested dictionary, set or list, return a sorted version.  Note that lists aren't sorted (they merely retain
    their original order).  Original data is unchanged.
    :param orig: original dict or list (may or may not be sorted)
    :return: sorted version of orig (note that we never return sets since they are unordered)
    """
    orig = copy.deepcopy(orig)
    if isinstance(orig, list):
        return [dls_sort(e) for e in orig]
    elif isinstance(orig, set):
        # have to sort sets to be consistent since they have no order
        return sorted(list(orig))
    elif isinstance(orig, dict) or isinstance(orig, collections.OrderedDict):
        sorted_dict = collections.OrderedDict()
        for k in sorted(orig):
            sorted_dict[k] = dls_sort(orig[k])
        return sorted_dict
    return orig