How to Simulate a Stable Sort Cursor in Python

Build a MongoDB-style cursor mock that stably sorts records by a key while preserving original order for ties, with next() and rewind() methods.

Medium Python 3.9+ Aug 9, 2026 Database scaling & optimization 13 views 0 copies

Python code

59 lines
Python 3.9+
```python
import random

class CursorStableSortMock:
    """Simulates stable sorting with a cursor-like pointer for MongoDB-style queries."""
    
    def __init__(self, data, sort_key, reverse=False):
        self.data = list(data)
        self.sort_key = sort_key
        self.reverse = reverse
        self._index = 0
        self._stable_sort()
    
    def _stable_sort(self):
        """Perform stable sort maintaining original order of equal elements."""
        indexed_data = list(enumerate(self.data))
        indexed_data.sort(key=lambda x: x[0], reverse=False)  # preserve original indices
            
        # Stable sort by key using sorting by (key, original_index)
        indexed_data.sort(
            key=lambda x: (x[1][self.sort_key], x[0]),
            reverse=self.reverse
        )
        self.data = [item for _, item in indexed_data]
    
    def next(self):
        """Return next item from cursor or None if exhausted."""
        if self._index >= len(self.data):
            return None
        result = self.data[self._index]
        self._index += 1
        return result
    
    def rewind(self):
        """Reset cursor to beginning."""
        self._index = 0


if __name__ == "__main__":
    test_data = [
        {"name": "alice", "score": 85},
        {"name": "bob", "score": 92},
        {"name": "carol", "score": 85},
        {"name": "dave", "score": 92},
        {"name": "eve", "score": 70},
    ]
    
    cursor = CursorStableSortMock(test_data, sort_key="score", reverse=True)
    
    while True:
        item = cursor.next()
        if item is None:
            break
        print(f"{item['name']}: {item['score']}")
    
    # Demonstrate cursor rewind
    cursor.rewind()
    first_item = cursor.next()
    print(f"\nFirst item after rewind: {first_item['name']}: {first_item['score']}")

Output

stdout
bob: 92
dave: 92
alice: 85
carol: 85
eve: 70

First item after rewind: bob: 92

How it works

The mock uses a two-step sort: first, it attaches original indices using enumerate(), then it sorts by (sort_key, original_index) as a tuple key. Sorting by the composite key guarantees stability even when the reverse flag is applied, because the tie-breaking index ensures equal keys retain their input order. The cursor wrapper adds stateful iteration with next() returning None at the end, and rewind() resetting the pointer for reuse. This mimics how database cursors lazily fetch sorted results in production queries.

Common mistakes

  • Using sort() directly on dicts without specifying a key function, which raises TypeError
  • Reversing the entire tuple sort, which also reverses tie order unexpectedly
  • Forgetting that sorting is a one-time operation; mutating the data after init won't re-sort
  • Applying a plain sort without the original index touchstone when stability matters

Variations

  1. Use operator.itemgetter(self.sort_key) as the sort key instead of a lambda for better performance
  2. Leverage functools.cmp_to_key for multi-field comparisons if the sort criteria is more complex

Real-world use cases

  • Paginating a large MongoDB query client-side, ensuring consistent ordering across pages when scores tie.
  • Testing application code that relies on stable sorting semantics before connecting to a real database.
  • Building an in-memory leaderboard service that sorts player scores while keeping submission order for equal values.

Sponsored

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Database scaling & optimization

Related tutorials and quizzes for this topic.