Sorting a Python dictionary with randomized tie breaker

SortingWithRandomizedTies.py

import random


def compare_with_ties(a, b):
    diff = cmp(a, b)
    return diff if diff else random.choice([-1, 1])

a = {'a': 1, 'b': 2, 'c': 1, 'd': 2, 'e': 1}

print "Initial dictionary:\n", str(a.items())

print "\nSorted without randomizing ties:"
print sorted(a.iteritems(), key=lambda (k, v): v)

print "\nSorted with randomized ties:"
print sorted(a.iteritems(), key=lambda (k, v): v, cmp=compare_with_ties)

# ---------- Sample Output ----------
# Initial dictionary:
# [('a', 1), ('c', 1), ('b', 2), ('e', 1), ('d', 2)]

# Sorted without randomizing ties:
# [('a', 1), ('c', 1), ('e', 1), ('b', 2), ('d', 2)]

# Sorted with randomized ties:
# [('c', 1), ('a', 1), ('e', 1), ('d', 2), ('b', 2)]

This is way faster, as it doesn't generate a list:

def int compare_with_ties(x, y):
    if x < y:
        return -1
    elif x > y:
        return 1
    else:
        return random.randint(0, 1) * 2 - 1

or if you need to use cmp

def int compare_with_ties(x, y):
    diff = cmp(x, y)
    if diff:
        return diff
    else:
        return random.randint(0, 1) * 2 - 1