Maintain a list sorted by multiple attributes?

Question

ss = [(0,'bb','jj'), (1,'aa','mm'), (2,'aa','kk'),(3,'bb','ee'),(4,'gg','ff')]

for x in ss:
    pp = <somthing>

Using Python, is it possible to insert from ss into pp and maintain pp sorted by two attributes, let's say by the 2nd then 3rd position in order to have the following result (both attributes ascending):

pp = [(2, 'aa', 'kk'), (1, 'aa', 'mm'), (3, 'bb', 'ee'), (0, 'bb', 'jj'), (4, 'gg', 'ff')]

Or (both attributes descending):

pp = [(4, 'gg', 'ff'), (0, 'bb', 'jj'), (3, 'bb', 'ee'), (1, 'aa', 'mm'), (2, 'aa', 'kk')]

I don't want to use the following two statments after the loop which already do the job:

pp = sorted(ss, key = operator.itemgetter(1, 2))
pp = sorted(ss, key = operator.itemgetter(1, 2), reverse=True)

Because i am dealing with a very long list and i already have the loop which i want to reuse for sorting as well.

Answer 1

You can use binary search during every insertion.

ss = [(0,'bb','jj'), (1,'aa','mm'), (2,'aa','kk'),(3,'bb','ee'),(4,'gg','ff')]

l = []

def insert_sort(l, e, compare):
    lo = 0
    hi = len(l)
    while lo < hi:
        mid = (lo+hi) / 2
        if compare(e, l[mid]):
            lo = mid + 1
        else: 
            hi = mid
    l.insert(lo, e)

ascend_list = []
descend_list = []

for i in ss:
    insert_sort(ascend_list, i, lambda x, y: x[1:] >= y[1:])

for i in ss:
    insert_sort(descend_list, i, lambda x, y: x[1:] < y[1:])

print ascend_list
print descend_list