Sort array of pairs by two different orders, without using built-in methods-CodePudding

I have a given array of pairs T = [[a1,b1],[a2,b2],...,[an,bn]] and I would like to sort it so that the elements b1,b2,...,bn are in ascending order and if some bs are equal sort 'a' elements in descending order

Example: for [1,6],[2,3],[5,7],[5,6],[2,5] the result should be like this: [2,3],[2,5],[5,6],[1,6],[5,7]

The problem is that I can't use any built-in functions, methods etc.

At first I thought to use twice some stable sorting, but I also care about execution time, isn't there any faster way to do it?

CodePudding user response：

Implement any simple sorting algorithm like InsertionSort, but instead of direct comparison of pairs use function like this:

def less(p1, p2):
   if p1[1] < p2[1]:
       return True
   elif p1[1] > p2[1]:  
       return False
   else:
       return p1[0] > p2[0]

If list size is large, then apply faster algo with the same comparison function

So instead of something like:

 while j >=0 and key < T[j] :

you have to write:

while j >=0 and less(key, T[j]):