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.iteritems())

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)