Data structure for multilevel vector function by attributes

I need to sort a vector with tuples

[(a_ _eleven, ..., a_ _1n), ..., (a_ _m1, ..., a_ _mn)]

based on a list of attributes and their comparison operators <or>. For example: sort a_ first ₂ using operator a> and a_ ₅₇ using <Operator.

Question . I'm looking for a data structure to do this efficiently on the assumption that sorting happens much more frequently than updates to a vector.

My current idea is to preserve the sort order for each attribute by adding linked-list-like pointers for each attribute:

For example, this vector:

0: (1, 7, 4)
1: (2, 5, 6)
2: (3, 4, 5)

      

        
        
        
      

    

Would get a data structure

0: (1 next:1 prev:-, 7 next:- prev:1, 4 next:2 prev:-)
1: (2 next:2 prev:1, 5 next:0 prev:2, 6 next:- prev:2)
2: (3 next:- prev:2, 4 next:1 prev:-, 5 next:1 prev:0)

      

        
        
        
      

    

Edit:

• I only need one sort order at any given time. After I get a user request for a different sort order, I need to recheck as quickly as possible.
• The step-by-step idea is very good, but I need to make an estimate of how much time I need, and it's easier if I have an idea how to do it.
• Once I'm done, I need random access to groups of 100 items, i.e. the first 100, the second 100, or 5100-5199 items.