Programa en C++ para ordenar arreglos excepto elementos en un subarreglo

Dada una array A enteros positivos, ordene la array en orden ascendente de modo que el elemento en la subarreglo dado (se ingresan los índices de inicio y final) en la array sin ordenar permanezca inmóvil y todos los demás elementos estén ordenados.
Ejemplos: 
 

Input : arr[] = {10, 4, 11, 7, 6, 20}
            l = 1, u = 3
Output : arr[] = {6, 4, 11, 7, 10, 20}
We sort elements except arr[1..3] which
is {11, 7, 6}. 

Input : arr[] = {5, 4, 3, 12, 14, 9};
            l = 1, u = 2;
Output : arr[] = {5, 4, 3, 9, 12, 14 }
We sort elements except arr[1..2] which
is {4, 3}. 

Enfoque: copie todos los elementos excepto el límite dado de una array dada a otra array. Luego ordene la otra array usando un algoritmo de clasificación. Finalmente, copie nuevamente la array ordenada a la array original. Mientras copia, omita el subarreglo dado.
 

// CPP program to sort all elements except
// given subarray.
#include <bits/stdc++.h>
using namespace std;
 
// Sort whole array a[] except elements in
// range a[l..r]
void sortExceptUandL(int a[], int l, int u, int n)
{
    // Copy all those element that need
    // to be sorted to an auxiliary
    // array b[]
    int b[n - (u - l + 1)];
    for (int i = 0; i < l; i++)
         b[i] = a[i];
    for (int i = u+1; i < n; i++)
         b[l + (i - (u+1))] = a[i];   
 
    // sort the array b
    sort(b, b + n - (u - l + 1));
 
    // Copy sorted elements back to a[]
    for (int i = 0; i < l; i++)
         a[i] = b[i];
    for (int i = u+1; i < n; i++)
         a[i] = b[l + (i - (u+1))];
}
 
// Driver code
int main()
{
    int a[] = { 5, 4, 3, 12, 14, 9 };
    int n = sizeof(a) / sizeof(a[0]);
    int l = 2, u = 4;
    sortExceptUandL(a, l, u, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
}

4 5 3 12 14 9

Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(n)

¡ Consulte el artículo completo sobre la clasificación de arrays excepto los elementos en una subarreglo para obtener más detalles!