алгоритм -Сортировка массива с LogLogN различных элементов

Это не моя школьная домашняя работа. Это моя собственная домашняя работа, и я самостоятельно -изучаю алгоритмы.

В Algorithm Design Manual есть такой акциз

4 -25 Предположим, что массив A[1..n] имеет только числа из {1,..., n ^ 2}, но что когда-либо появляется не более log log n этих чисел. Разработайте алгоритм, который сортирует A по существенно меньшему, чем O (n log n ).

У меня есть два подхода.:

Первый подход.:

По сути, я хочу выполнить сортировку подсчетом для этой задачи. Я могу сначала просмотреть весь массив (O (N ))и поместить все различные числа в массив размера loglogN (int[] K ).

Затем примените сортировку подсчетом. Однако при настройке массива подсчета (int[] C )мне не нужно устанавливать его размер как N^2, вместо этого я также устанавливаю размер как loglogN.

Но таким образом, при подсчете частот каждого отдельного числа,Мне нужно просканировать массив K, чтобы получить индекс этого элемента (O (NloglogN ), а затем обновить массив C.

Второй подход:

Опять же, мне нужно просканировать весь массив, чтобы получить отчетливый числовой массив K размером loglogN.

Затем я просто выполняю что-то вроде быстрой сортировки, но разбиение основано на медиане массива K (, т. е. каждый раз, когда точка опоры является элементом массива K ), рекурсивно.

Я думаю, что этот подход будет лучшим, с O (NlogloglogN ).

Я прав? или есть лучшие решения?

Подобные акцизы существуют в Руководстве по проектированию алгоритмов, например

4 -22 Покажите, что n положительных целых чисел в диапазоне от 1 до k можно отсортировать за время O (n log k ). Интересен случай, когда k

4 -23 Мы пытаемся отсортировать последовательность S из n целых чисел с большим количеством повторений, так что количество различных целых чисел в S равно O (log n ). Предложите алгоритм времени O (n log log n )наихудшего -случая для сортировки таких последовательностей.

Но в основном для всех этих акцизов моя интуиция всегда думала о сортировке подсчетом, поскольку мы можем знать диапазон элементов, а диапазон достаточно короток по сравнению с длиной всего массива. Но после более глубокого размышления, я думаю, акцизам нужен второй подход, верно?

Спасибо