Dada una array A[] de tamaño N , la tarea es ordenar la array en orden creciente utilizando In-Place Merge Sort .
Ejemplos:
Entrada: A = {5, 6, 3, 2, 1, 6, 7}
Salida: {1, 2, 3, 5, 6, 6, 7}Entrada: A = {2, 3, 4, 1}
Salida: {1, 2, 3, 4}
Enfoque: la idea es usar la función inplace_merge() para fusionar las arrays ordenadas en el espacio O(1) . Siga los pasos a continuación para resolver el problema:
- Cree una función recursiva mergeSort() que acepte los índices inicial y final de la array como parámetros. Ahora, realiza los siguientes pasos:
- Si el tamaño de la array es igual a 1, simplemente regrese de la función .
- De lo contrario, calcule el índice medio para dividir la array en dos subarreglos.
- Llame recursivamente a mergeSort() en los subarreglos izquierdo y derecho para ordenarlos por separado.
- Luego, llame a la función inplace_merge() para fusionar los dos subarreglos.
- Después de completar los pasos anteriores, imprima la array ordenada A[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define it vector<int>::iterator
using namespace std;
// Recursive function to split the array
// into two subarrays and sort them
void mergeSortUtil(it left, it right)
{
// Handle the base case
if (right - left <= 1)
return;
// Otherwise, find the middle index
it mid = left + (right - left) / 2;
// Recursively sort
// the left subarray
mergeSortUtil(left, mid);
// Recursively sort
// the right subarray
mergeSortUtil(mid, right);
// Merge the two sorted arrays using
// inplace_merge() function
inplace_merge(left, mid, right);
return;
}
// Function to sort the array
// using inplace Merge Sort
void mergeSort(vector<int> arr)
{
// Recursive function to sort the array
mergeSortUtil(arr.begin(), arr.end());
// Print the sorted array
for (int el : arr)
cout << el << " ";
}
// Driver Code
int main()
{
vector<int> arr = { 5, 6, 3, 2, 1, 6, 7 };
mergeSort(arr);
return 0;
}
1 2 3 5 6 6 7
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)
Enfoques alternativos: Consulte el artículo anterior para conocer otros enfoques para resolver este problema.
Publicación traducida automáticamente
Artículo escrito por abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA