Распределение в выборке не случайно и предсказуемо. Этим пользуются. Можно сначала разложить по корзинам(basket sort) или порядку цены (radix sort). Это даст существенный прирост производительности, если именно он вас интересует(до линейной n, против христоматийных n*log(n)). Если сортировать по дате, то выборка будет частично упорядочена(да и по цене вы написали)-на частично упорядоченных массивах простая сортировка вставкой (insertion sort) самая эффективная. Впрочем встроенный уже в stdlib Python и Java новомодный TimSort старается использовать обе оптимизации.
Средний
