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