Как я получаю размер каталога в C?

Не существует способа сортировки с O (n) сложностью по времени. Посмотрите на сложность наихудшего случая для популярных алгоритмов в Википедии.

Лучшая временная сложность в худшем случае - O (nlogn). Вот как мы можем решить это за O (nlogn) сложность времени:

    let array = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]

    extension Array where Element: Comparable & Hashable {
        func countableSorted() -> [Element] {
            var counts = [Element: Int]()
            // O(n)
            for element in self {
                counts[element] = (counts[element] ?? 0) + 1
            }

            // I think that standart method uses O(nlogn) time complexity.
            // O(nlogn) + O(n) approximately equal to O(nlogn).
            let sorted = counts.sorted { item1, item2 -> Bool in
                if item2.value > item1.value {
                    return true
                }

                if item2.value == item1.value {
                    return item2.key > item1.key
                }

                return false
            }

            var result = [Element]()
            // O(n)
            for item in sorted {
                let items = Array(repeating: item.key, count: item.value)
                result.append(contentsOf: items)
            }

            // Total time complexity for worst case scenario is O(nlogn)

            return result
        }
    }

    print(array.countableSorted())

    // Output: [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]