An implementation of weighted random selection in python. O(n*log(n))

weighted_random.py

import random

# This method randomly picks a single choice from a collection of choices.
# freq_tuples: List of tuples of the form: (choice, count)
# Returns a choice, or None if empty list.
def weighted_random_selection(freq_tuples):
    if len(freq_tuples) == 1:
        return freq_tuples[0][0]
    sorted_freq_tuples = sorted(freq_tuples, key = lambda tup : tup[1], reverse=True)
    total = sum([count for gram, count in freq_tuples]) * random.random()
    for gram, count in sorted_freq_tuples:
        total -= count
        if (total < 0):
            return gram
    return None

weighted_random_sample.py

# sample
choices = [('x', 1), ('y', 1), ('z', 2), ('a', 0)]

pick_counts = {'x': 0, 'y': 0, 'z': 0, 'a': 0}
trials = 100000

for i in range(trials):
    choice = weighted_random_selection(choices)
    pick_counts[choice] += 1

for pick in sorted(pick_counts.keys()):
    print (pick, 1.0 * pick_counts[pick] / trials)

note for me: Might this work without the sorting? Can this be brought down to O(n)?