big_sorting.py

# source: https://www.hackerrank.com/challenges/big-sorting/problem
# video: https://youtu.be/0KJhHCIuoG0
def bigSorting(unsorted):
    # Chunk values into separate sizes
    cache = {}
    for val in unsorted: # O(n), max of 2*10^5
        n = len(val)
        if n not in cache:
            cache[n] = []
        cache[n].append(val)
    # Sort the lengths
    sizes = sorted(cache.keys()) # O(10^6) = O(1)
    output = []
    # For each length, sort it's list and add to growing output list
    for size in sizes: # O(10^6) = O(1)
        vals = cache[size]
        vals.sort() # O(nlogn) where n is the size of the list (max of 2*10^5)
        output.extend(vals)
    return output # O(n) + O(nlogn) = O(nlogn)