Motivation

Counting Sort asla iki öğeyi karşılaştırmaz. Değerlerini doğrudan bir count dizisi için dizin (index) olarak kullanır; bu da onun doğrusal zamanda (linear time) çalışmasını sağlayan şeydir.

Neden Counting Sort öğrenilmeli?

• Doğrusal zaman: n öğe sayısı ve k değer aralığı olmak üzere O(n + k) süresinde çalışır. k küçük olduğunda, bu O(n log n) karmaşıklığını geride bırakır.
• Kararlı (dikkatli yapıldığında): Birkaç counting-sort geçişini birbirine bağlayan Radix Sort için bir temel oluşturur.
• Farklı bir fikir: Değerleri karşılaştırmak yerine onları sayarak (çetele tutarak) sıralama.

Ödünleşim: count dizisi için O(k) belleğe ihtiyaç duyar, bu nedenle değer aralığı çok büyük olduğunda (örneğin, bir milyara kadar olan birkaç sayıyı sıralamak gibi) pek uygun değildir.