изменение алгоритма сортировки массива черного ящика на стабильный алгоритм

Question

пусть Sort1 будет заданным алгоритмом, а A - заданным массивом. Сортировка 1 выполняется во время f (n). Мне нужно создать новый стабильный алгоритм, Sort2, используя Sort1, который будет работать во время f (n) + O (n).

У меня есть решение, предложенное моим другом:

• Создание массива клонов B из A.
• Замена каждого числа в B на пару (число, индекс), где число - это число (элемент), а index - это его индекс (местоположение в A).
• каждый элемент в B указывает на соответствующий элемент в A.
• запустить Sort1 на A.
• для каждой последовательности одинаковых чисел в отсортированном A, запустите Sort1 на флэш-памяти, которая будет сортировать флэш-память по индексу каждого элемента.

верно ли его решение? У вас есть какие-нибудь предложения? спасибо!

Answer 1

Сделайте копию, но затем создайте новую функцию сравнения, которая использует исходные данные в качестве первичного ключа (возможно, даже используя исходную функцию сравнения для выполнения сравнения), и, если она равна, сделайте вторичное сравнение на основе исходная позиция в массиве.