Once again about one-liners

frequency_sort.py

from itertools import groupby
from functools import reduce
import time


def frequency_sort(items):
    # {elem: first_occurrence_index}
    occurrences = {}
    for idx, val in enumerate(items):
        if val not in occurrences:
            occurrences[val] = idx

    # [(elem, count, index),]
    groups = [(key, len(list(grp)), occurrences[key]) for key, grp in groupby(sorted(items))]

    # sorting by count (bigger first) and index (lesser first)
    sorted_grps = sorted(groups, key=lambda x: (x[1], -x[2]), reverse=True)

    result = []
    for val, count, _ in sorted_grps:
        result.extend([val for _ in range(count)])

    return result


def one_line_frequency_sort(items):
    return sorted(items, key=lambda x: (-items.count(x), items.index(x)))

if __name__ == '__main__':
    items = [5 for _ in range(100000)] + [4 for _ in range(100000)] + [9 for _ in range(100000)]
    start = time.time()
    frequency_sort(items)
    exec_time = time.time() - start

    start = time.time()
    one_line_frequency_sort(items)
    exec_time1 = time.time() - start

    print("exec_time = {}".format(exec_time))
    print("exec_time1 = {}".format(exec_time1))

Output:
exec_time = 0.0454747676849
exec_time1 = 1371.25308895