Я думаю, что вы хотите получить ответ "нет", но я также думаю, что вы, возможно, захотите рассмотреть свой вопрос более тщательно.
Проблема в том, что вы используете непрерывные координаты, поэтому в принципе вы не можете использовать линейную сортировку. (На практике вы можете использовать, скажем, сортировку по основанию для обработки координаты фиксированного размера, но на практике это может быть на самом деле медленнее, чем стандартная сортировка O (N log N), из-за накладных расходов ...)
Теоретическое правило: всякий раз, когда у вас есть ситуация, когда вы можете сравнивать только свои значения, общая сортировка не может быть быстрее, чем O (N log N).
Вы упомянули неуказанное свойство, которое "могло бы эксплуатироваться большую часть времени". Проблема в том, что запись O () является асимптотическим, наихудшим, теоретическим свойством, поэтому «большую часть времени» не будет иметь значения. Определенное свойство ввода часто можно использовать таким образом, но:
- ускорение O () очень чувствительно к тому, что именно ваша собственность
- алгоритм с лучшей O () может быть намного медленнее для вашего практического применения
- наиболее эффективный метод практического использования вашего ввода часто очень отличается от метода с лучшими асимптотическими свойствами
К сожалению, при настройке вашего алгоритма для использования ваших входных данных легко пропустить неясный сценарий наихудшего случая, который неожиданно убьет вашу производительность, еще долго после того, как вы ее выпустили. Самая важная вещь в O () вашего алгоритма - не дать ему сильно взорваться.
Обратите внимание, что для этой цели O (N log N) равняется почти линейному, и использование стандартной библиотеки библиотек с хорошим поведением вполне может быть правильным выбором.