﻿Implement a sorting algorithm with the following requirements:
1. Must be a comparison-based sort.
2. Must run in O(n) worst-case time complexity.
3. Must be stable (preserve relative order of equal elements).
4. Must sort in-place (O(1) extra space).
