Foro de elhacker.net

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.

#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/ (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?

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.