Efficient way to find the average of the rank of added scores to a list. Possibly a more efficient way of sorting or a math way?
Question: I am trying to solve a problem where I need to find the average of the ranks
of a bunch of scores added to a list.

For example if the input is: 5 100 200 150 170 50

Then the program should output 2.2

There are 5 scores to be added

When 100 is entered it is ranked 1

When 200 is entered it is ranked 1

When 150 is entered it is ranked 2

When 170 is entered it is ranked 2

when 50 is entered it is ranked 5

Then (1 + 1 + 2 + 2 + 5) = 2.2

Right now I have a solution that works perfectly but It is not fast enough for
large test cases.

    
    
    games = input()
    lst = []
    acc = 0.0
    counter = 0.0
    for i in range(0, games):
        number = input()
        lst.append(number)
        lstt = sorted(lst)
        lsttt = lstt[::-1]
        acc += (lsttt.index(number) + 1)
    print acc / games
    

Right now i am using the default python sort function, and I'm thinking using
a different kind of sort could make it faster. Is that the issue or is there a
better math way to do it?


Answer: You could use the [`bisect`](https://docs.python.org/2/library/bisect.html)
module to find the insertion point in `O(log(n))` time:

    
    
    import bisect
    
    games = input()
    lst = []
    acc = 0.0
    counter = 0.0
    for i in range(games):
        number = input()
        pos = bisect.bisect(lst, number)
        lst.insert(pos, number)  # O(log(n)) for the search, but O(n) for the insertion
        acc += len(lst) - pos
    print acc / games
    

It's an improvement over your algorithm in that it's `O(n^2)` rather than
`O((n^2)*log(n))`. If that's still too slow, you might want to consider using
a tree.

