I am kind of hitting a wall on this problem and I was wondering if some fresh brains could help me out.
I have a large list of four element tuples in the format:
(ID number, Type, Start Index, End Index) 
Previously in the code, I have searched through thousands of blocks of text for two specific types of substrings. These tuples store in which large chunk of text the substring was found, which of the two types of substrings it is, and the start and end index of this substring.
The final goal is to look through this list to find all instances where a type 1 substring occurs before a type 2 substring in a block of text with the same ID. Then I would like to store these objects in the format (ID, Type 1, Start, End, Type2, Start, End).
I've tried to mess around with a bunch of stuff that was super inefficient. I have the list sorted by ID then Start Index, and if been trying varying ways of popping the items off the list for comparisons. I have to imagine there is a more elegant solution. Any brilliant people out there wish to assist my tired brain???
Thanks in advance
Assuming there are lots of entries for each ID, I would (pseudo-code)

    for each ID:
        for each type2 substring of that ID:
            store it in an ordered list, sorted by start point
        for each type1 substring of that ID:
            calculate the end point (or whatever)
            look it up in the ordered list
            if there's anything to the right, you have a hit

So, if you have control of the initial sort, then instead of (ID, start), you want them sorted by ID, then by type (2 before 1). Then within the type, sort by start point for type2, and the offset you're going to compare for type1. I'm not sure whether by "A before B" you mean "A starts before B starts" or "A ends before B starts", but do whatever's appropriate. 
Then you can do the whole operation by running over the list once. You don't need to actually construct an index of type2s, because they're already in order. Since the type1s are sorted too, you can do each lookup with a linear or binary search starting from the result of the previous search. Use a linear search if there are lots of type1s compared with type2s (so results are close together), and a binary search if there are lots of type2s compared with type1s (so results are sparse). Or just stick with the linear search as it's simpler - this lookup is the inner loop, but its performance might not be critical.
If you don't have control of the sort, then I don't know whether it's faster to build the list of type2 substrings for each ID as you go; or to sort the entire list before you start into the required order; or just to work with what you've got, by writing a "lookup" that ignores the type1 entries when searching through the type2s (which are already sorted as required). Test it, or just do whatever results in clearer code. Even without re-sorting, you can still use the merge-style optimisation unless "sorted by start index" is the wrong thing for the type1s.
Efficient Tuple List Comparisons