Сортування підрахунком і порозрядне сортування

Коротко: Сортування підрахунком і порозрядне сортування працюють без порівнянь і тому можуть бути швидшими за O(n log n), якщо ключі — цілі числа з невеликого діапазону.

Докладніше: Методи на порівняннях, такі як швидке сортування, ніколи не можуть бути кращими за O(n log n). Використання властивостей ключів обходить цю межу.

Подробиці

• Сортування підрахунком: Рахує, скільки разів трапляється кожне значення (масив розміру k), обчислює з цього початкові позиції та записує елементи туди. Час O(n + k), стійке.
• Межа: Якщо діапазон значень k величезний (наприклад, 64-бітні числа), масив підрахунку непридатний.
• Порозрядне сортування: Сортує по розрядах, від молодшого до старшого, щоразу стійким методом на кшталт сортування підрахунком. Час O(d · (n + b)) за d розрядів і основи b.
• Приклад: 32-бітні числа з основою 256: лише чотири проходи.
• Застосування: Сортування ідентифікаторів, поштових індексів, рядків фіксованої довжини, графічні конвеєри.
• Ціна: Додаткова пам’ять і залежність від типу ключа.

Див. також: O-нотація, Сортування