¿Cómo hallar una Permutacion ordenada con MergeSort?

[_TTFH_3500]

Dado un arreglo desordenado con n elementos, el siguiente código retorna una permutación tal que al aplicarla al arreglo original los elementos quedan ordenados.

Código (cpp) [Seleccionar] Expandir

#include <stdio.h>

typedef unsigned int uint;

void Swap(int &a, int &b) {
int t = a;
a = b;
b = t;
}

int* BubbleSort(const int* A, uint n) {
int* P = new int[n];
for (uint i = 0; i < n; i++)
P[i] = i;
bool ordenado;
do {
ordenado = true;
for (uint i = 1; i < n; i++)
if (A[P[i-1]] > A[P[i]]) {
Swap(P[i-1], P[i]);
ordenado = false;
}
} while (!ordenado);
return P;
}

int main() {
uint n;
printf("Ingrese la cantidad de numeros: ");
scanf("%u", &n);
printf("Ingrese los numeros:\n");
int* A = new int[n];
for (uint i = 0; i < n; i++)
scanf("%d", &A[i]);
int* P = BubbleSort(A, n);
printf("Los numeros ordenados son:\n");
for (uint i = 0; i < n; i++)
printf("%d ", A[P[i]]);
printf("\n");
delete[] A;
delete[] P;
return 0;
}

Pero lo hace en tiempo O(n^2), en cambio el siguiente codigo: https://www.geeksforgeeks.org/merge-sort/ retorna el arreglo ordenado en tiempo O(n log(n))
¿Cómo puedo modificar MergeSort para obtener una permutación ordenada en lugar de ordenar el propio arreglo?

[CalgaryCorpus]

Aplica la misma idea que muestras aquí, mantén un arreglo de índices y compara la desrefencia. Cuánto corresponda mover o intercambiar, lo haces en el arreglo de índices.