Implemente Merge Sort , es decir, implementación estándar manteniendo el algoritmo de clasificación en su lugar.
In situ significa que no ocupa memoria adicional para la operación de fusión como en el caso estándar.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 1}
Salida: 1 2 3 4Entrada: arr[] = {56, 2, 45}
Salida: 2 45 56
Enfoque 1:
- Mantenga dos punteros que apunten al inicio de los segmentos que deben fusionarse.
- Compare los elementos en los que están presentes los punteros.
- Si element1 < element2 entonces element1 está en la posición correcta, simplemente aumente pointer1 .
- De lo contrario, mueva todos los elementos entre el elemento 1 y el elemento 2 (incluido el elemento 1 pero excluyendo el elemento 2) a la derecha en 1 y luego coloque el elemento 2 en el lugar anterior (es decir, antes de cambiar a la derecha) del elemento 1. Incrementa todos los punteros en 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program in-place Merge Sort
#include <iostream>
using namespace std;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
void merge(int arr[], int start, int mid, int end)
{
int start2 = mid + 1;
// If the direct merge is already sorted
if (arr[mid] <= arr[start2]) {
return;
}
// Two pointers to maintain start
// of both arrays to merge
while (start <= mid && start2 <= end) {
// If element 1 is in right place
if (arr[start] <= arr[start2]) {
start++;
}
else {
int value = arr[start2];
int index = start2;
// Shift all the elements between element 1
// element 2, right by 1.
while (index != start) {
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
cout <<" "<< A[i];
cout <<"\n";
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, arr_size - 1);
printArray(arr, arr_size);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C++ program in-place Merge Sort
#include <stdio.h>
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
void merge(int arr[], int start, int mid, int end)
{
int start2 = mid + 1;
// If the direct merge is already sorted
if (arr[mid] <= arr[start2]) {
return;
}
// Two pointers to maintain start
// of both arrays to merge
while (start <= mid && start2 <= end) {
// If element 1 is in right place
if (arr[start] <= arr[start2]) {
start++;
}
else {
int value = arr[start2];
int index = start2;
// Shift all the elements between element 1
// element 2, right by 1.
while (index != start) {
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, arr_size - 1);
printArray(arr, arr_size);
return 0;
}
Java
// Java program in-place Merge Sort
public class GFG {
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
static void merge(int arr[], int start, int mid,
int end)
{
int start2 = mid + 1;
// If the direct merge is already sorted
if (arr[mid] <= arr[start2]) {
return;
}
// Two pointers to maintain start
// of both arrays to merge
while (start <= mid && start2 <= end) {
// If element 1 is in right place
if (arr[start] <= arr[start2]) {
start++;
}
else {
int value = arr[start2];
int index = start2;
// Shift all the elements between element 1
// element 2, right by 1.
while (index != start) {
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
static void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
static void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
System.out.print(A[i] + " ");
System.out.println();
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = arr.length;
mergeSort(arr, 0, arr_size - 1);
printArray(arr, arr_size);
}
// This code is contributed by ANKITRAI1
}
Python3
# Python program in-place Merge Sort # Merges two subarrays of arr. # First subarray is arr[l..m] # Second subarray is arr[m+1..r] # Inplace Implementation def merge(arr, start, mid, end): start2 = mid + 1 # If the direct merge is already sorted if (arr[mid] <= arr[start2]): return # Two pointers to maintain start # of both arrays to merge while (start <= mid and start2 <= end): # If element 1 is in right place if (arr[start] <= arr[start2]): start += 1 else: value = arr[start2] index = start2 # Shift all the elements between element 1 # element 2, right by 1. while (index != start): arr[index] = arr[index - 1] index -= 1 arr[start] = value # Update all the pointers start += 1 mid += 1 start2 += 1 ''' * l is for left index and r is right index of the sub-array of arr to be sorted ''' def mergeSort(arr, l, r): if (l < r): # Same as (l + r) / 2, but avoids overflow # for large l and r m = l + (r - l) // 2 # Sort first and second halves mergeSort(arr, l, m) mergeSort(arr, m + 1, r) merge(arr, l, m, r) ''' UTILITY FUNCTIONS ''' ''' Function to print an array ''' def printArray(A, size): for i in range(size): print(A[i], end=" ") print() ''' Driver program to test above functions ''' if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] arr_size = len(arr) mergeSort(arr, 0, arr_size - 1) printArray(arr, arr_size) # This code is contributed by 29AjayKumar
C#
// C# program in-place Merge Sort
// sum.
using System;
class GFG {
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
static void merge(int[] arr, int start, int mid,
int end)
{
int start2 = mid + 1;
// If the direct merge is already sorted
if (arr[mid] <= arr[start2]) {
return;
}
// Two pointers to maintain start
// of both arrays to merge
while (start <= mid && start2 <= end) {
// If element 1 is in right place
if (arr[start] <= arr[start2]) {
start++;
}
else {
int value = arr[start2];
int index = start2;
// Shift all the elements between element 1
// element 2, right by 1.
while (index != start) {
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
static void mergeSort(int[] arr, int l, int r)
{
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
static void printArray(int[] A, int size)
{
int i;
for (i = 0; i < size; i++)
Console.Write(A[i] + " ");
Console.WriteLine();
}
/* Driver code */
public static void Main(String[] args)
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
int arr_size = arr.Length;
mergeSort(arr, 0, arr_size - 1);
printArray(arr, arr_size);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program in-place Merge Sort
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
function merge(arr, start, mid, end)
{
let start2 = mid + 1;
// If the direct merge is already sorted
if (arr[mid] <= arr[start2])
{
return;
}
// Two pointers to maintain start
// of both arrays to merge
while (start <= mid && start2 <= end)
{
// If element 1 is in right place
if (arr[start] <= arr[start2])
{
start++;
}
else
{
let value = arr[start2];
let index = start2;
// Shift all the elements between element 1
// element 2, right by 1.
while (index != start)
{
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
/* l is for left index and r is right index
of the sub-array of arr to be sorted */
function mergeSort(arr, l, r)
{
if (l < r)
{
// Same as (l + r) / 2, but avoids overflow
// for large l and r
let m = l + Math.floor((r - l) / 2);
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
function printArray(A, size)
{
let i;
for(i = 0; i < size; i++)
document.write(A[i] + " ");
document.write("<br>");
}
// Driver code
let arr = [ 12, 11, 13, 5, 6, 7 ];
let arr_size = arr.length;
mergeSort(arr, 0, arr_size - 1);
printArray(arr, arr_size);
// This code is contributed by rag2127
</script>
Producción
5 6 7 11 12 13
Nota: la complejidad del tiempo del enfoque anterior es O (n 2 * log (n)) porque la combinación es O (n 2 ). La complejidad de tiempo de la ordenación por fusión estándar es menor, O(n Log n).
Enfoque 2: La idea: Comenzamos comparando elementos que están alejados entre sí en lugar de adyacentes. Básicamente, estamos usando la ordenación de shell para fusionar dos arrays ordenadas con O(1) espacio adicional .
mergeSort():
- Calcule mid two divida la array en dos mitades (sub-array izquierda y sub-array derecha)
- Llame recursivamente a la ordenación por combinación en el subconjunto izquierdo y el subconjunto derecho para ordenarlos
- Llame a la función de fusión para fusionar el subconjunto izquierdo y el subconjunto derecho
unir():
- Para cada pasada, calculamos el espacio y comparamos los elementos hacia la derecha del espacio.
- Inicie la brecha con un valor máximo de n/2, donde n es la longitud combinada del subarreglo izquierdo y derecho.
- En cada pasada, el espacio se reduce al valor máximo de espacio/2.
- Tome un puntero i para pasar la array.
- Intercambie los elementos i-ésimo y (i+brecha) si el elemento (i+brecha) es menor que (o mayor que al ordenar en orden decreciente) el elemento i.
- Deténgase cuando (i+brecha) llegue a n.
Entrada: 10, 30, 14, 11, 16, 7, 28
Nota: suponga que los subarreglos izquierdo y derecho se han ordenado, por lo que estamos fusionando los subarreglos ordenados [10, 14, 30] y [7, 11, 16, 28]
Empezar con
brecha = techo de n/2 = 7/2 = 4
[Esta brecha es para toda la array fusionada]
10 , 14, 30, 7, 11 , 16, 28
10, 14 , 30, 7, 11, 16 , 28
10, 14, 30 , 7, 11, 16, 28
10, 14, 28, 7, 11, 16, 30
brecha = techo de 4/2 = 2
10 , 14, 28 , 7, 11, 16, 30
10, 14 , 28, 7 , 11, 16, 30
10, 7, 28 , 14, 11 , 16, 30
10, 7, 11, 14 , 28, 16 , 30
10, 7, 11, 14, 28 , 16, 30
brecha = techo de 2/2 = 1
10 , 7 , 11, 14, 28, 16, 30
7, 10 , 11 , 14, 28, 16, 30
7, 10, 11 , 14 , 28, 16, 30
7, 10, 11, 14 , 28 , 16, 30
7, 10, 11, 14, 28 , 16 , 30
7, 10, 11, 14, 16, 28 , 30
Salida: 7, 10, 11, 14, 16, 28, 30
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Calculating next gap
int nextGap(int gap)
{
if (gap <= 1)
return 0;
return (int)ceil(gap / 2.0);
}
// Function for swapping
void swap(int nums[], int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Merging the subarrays using shell sorting
// Time Complexity: O(nlog n)
// Space Complexity: O(1)
void inPlaceMerge(int nums[], int start,
int end)
{
int gap = end - start + 1;
for(gap = nextGap(gap);
gap > 0; gap = nextGap(gap))
{
for(int i = start; i + gap <= end; i++)
{
int j = i + gap;
if (nums[i] > nums[j])
swap(nums, i, j);
}
}
}
// merge sort makes log n recursive calls
// and each time calls merge()
// which takes nlog n steps
// Time Complexity: O(n*log n + 2((n/2)*log(n/2)) +
// 4((n/4)*log(n/4)) +.....+ 1)
// Time Complexity: O(logn*(n*log n))
// i.e. O(n*(logn)^2)
// Space Complexity: O(1)
void mergeSort(int nums[], int s, int e)
{
if (s == e)
return;
// Calculating mid to slice the
// array in two halves
int mid = (s + e) / 2;
// Recursive calls to sort left
// and right subarrays
mergeSort(nums, s, mid);
mergeSort(nums, mid + 1, e);
inPlaceMerge(nums, s, e);
}
// Driver Code
int main()
{
int nums[] = { 12, 11, 13, 5, 6, 7 };
int nums_size = sizeof(nums) / sizeof(nums[0]);
mergeSort(nums, 0, nums_size-1);
for(int i = 0; i < nums_size; i++)
{
cout << nums[i] << " ";
}
return 0;
}
// This code is contributed by adityapande88
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class InPlaceMerge {
// Calculating next gap
private static int nextGap(int gap)
{
if (gap <= 1)
return 0;
return (int)Math.ceil(gap / 2.0);
}
// Function for swapping
private static void swap(int[] nums, int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Merging the subarrays using shell sorting
// Time Complexity: O(nlog n)
// Space Complexity: O(1)
private static void inPlaceMerge(int[] nums, int start,
int end)
{
int gap = end - start + 1;
for (gap = nextGap(gap); gap > 0;
gap = nextGap(gap)) {
for (int i = start; i + gap <= end; i++) {
int j = i + gap;
if (nums[i] > nums[j])
swap(nums, i, j);
}
}
}
// merge sort makes log n recursive calls
// and each time calls merge()
// which takes nlog n steps
// Time Complexity: O(n*log n + 2((n/2)*log(n/2)) +
// 4((n/4)*log(n/4)) +.....+ 1)
// Time Complexity: O(logn*(n*log n))
// i.e. O(n*(logn)^2)
// Space Complexity: O(1)
private static void mergeSort(int[] nums, int s, int e)
{
if (s == e)
return;
// Calculating mid to slice the
// array in two halves
int mid = (s + e) / 2;
// Recursive calls to sort left
// and right subarrays
mergeSort(nums, s, mid);
mergeSort(nums, mid + 1, e);
inPlaceMerge(nums, s, e);
}
// Driver Code
public static void main(String[] args)
{
int[] nums = new int[] { 12, 11, 13, 5, 6, 7 };
mergeSort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
}
Python3
# Python3 program for the above approach import math # Calculating next gap def nextGap(gap): if gap <= 1: return 0 return int(math.ceil(gap / 2)) # Function for swapping def swap(nums, i, j): temp = nums[i] nums[i] = nums[j] nums[j] = temp # Merging the subarrays using shell sorting # Time Complexity: O(nlog n) # Space Complexity: O(1) def inPlaceMerge(nums,start, end): gap = end - start + 1 gap = nextGap(gap) while gap > 0: i = start while (i + gap) <= end: j = i + gap if nums[i] > nums[j]: swap(nums, i, j) i += 1 gap = nextGap(gap) # merge sort makes log n recursive calls # and each time calls merge() # which takes nlog n steps # Time Complexity: O(n*log n + 2((n/2)*log(n/2)) + # 4((n/4)*log(n/4)) +.....+ 1) # Time Complexity: O(logn*(n*log n)) # i.e. O(n*(logn)^2) # Space Complexity: O(1) def mergeSort(nums, s, e): if s == e: return # Calculating mid to slice the # array in two halves mid = (s + e) // 2 # Recursive calls to sort left # and right subarrays mergeSort(nums, s, mid) mergeSort(nums, mid + 1, e) inPlaceMerge(nums, s, e) # UTILITY FUNCTIONS # Function to print an array def printArray(A, size): for i in range(size): print(A[i], end = " ") print() # Driver Code if __name__ == '__main__': arr = [ 12, 11, 13, 5, 6, 7 ] arr_size = len(arr) mergeSort(arr, 0, arr_size - 1) printArray(arr, arr_size) # This code is contributed by adityapande88
C#
// C# program for the above approach
// Include namespace system
using System;
using System.Linq;
using System.Collections;
public class InPlaceMerge
{
// Calculating next gap
private static int nextGap(int gap)
{
if (gap <= 1) {
return 0;
}
return (int)Math.Ceiling(gap / 2.0);
}
// Function for swapping
private static void swap(int[] nums, int i, int j)
{
var temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Merging the subarrays using shell sorting
// Time Complexity: O(nlog n)
// Space Complexity: O(1)
private static void inPlaceMerge(int[] nums, int start,
int end)
{
var gap = end - start + 1;
for (gap = InPlaceMerge.nextGap(gap); gap > 0;
gap = InPlaceMerge.nextGap(gap)) {
for (int i = start; i + gap <= end; i++) {
var j = i + gap;
if (nums[i] > nums[j]) {
InPlaceMerge.swap(nums, i, j);
}
}
}
}
// merge sort makes log n recursive calls
// and each time calls merge()
// which takes nlog n steps
// Time Complexity: O(n*log n + 2((n/2)*log(n/2)) +
// 4((n/4)*log(n/4)) +.....+ 1)
// Time Complexity: O(logn*(n*log n))
// i.e. O(n*(logn)^2)
// Space Complexity: O(1)
private static void mergeSort(int[] nums, int s, int e)
{
if (s == e) {
return;
}
// Calculating mid to slice the
// array in two halves
var mid = (int)((s + e) / 2);
// Recursive calls to sort left
// and right subarrays
InPlaceMerge.mergeSort(nums, s, mid);
InPlaceMerge.mergeSort(nums, mid + 1, e);
InPlaceMerge.inPlaceMerge(nums, s, e);
}
// Driver Code
public static void Main(String[] args)
{
int[] nums = new int[] { 12, 11, 13, 5, 6, 7 };
InPlaceMerge.mergeSort(nums, 0, nums.Length - 1);
Console.WriteLine(string.Join(", ", nums));
}
}
// This code is contributed by mukulsomukesh
Javascript
<script>
// Javascript program for the above approach
// Calculating next gap
function nextGap(gap)
{
if (gap <= 1)
return 0;
return Math.floor(Math.ceil(gap / 2.0));
}
// Function for swapping
function swap(nums,i,j)
{
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Merging the subarrays using shell sorting
// Time Complexity: O(nlog n)
// Space Complexity: O(1)
function inPlaceMerge(nums,start,end)
{
let gap = end - start + 1;
for (gap = nextGap(gap); gap > 0;
gap = nextGap(gap)) {
for (let i = start; i + gap <= end; i++) {
let j = i + gap;
if (nums[i] > nums[j])
swap(nums, i, j);
}
}
}
// merge sort makes log n recursive calls
// and each time calls merge()
// which takes nlog n steps
// Time Complexity: O(n*log n + 2((n/2)*log(n/2)) +
// 4((n/4)*log(n/4)) +.....+ 1)
// Time Complexity: O(logn*(n*log n))
// i.e. O(n*(logn)^2)
// Space Complexity: O(1)
function mergeSort(nums,s,e)
{
if (s == e)
return;
// Calculating mid to slice the
// array in two halves
let mid = Math.floor((s + e) / 2);
// Recursive calls to sort left
// and right subarrays
mergeSort(nums, s, mid);
mergeSort(nums, mid + 1, e);
inPlaceMerge(nums, s, e);
}
// Driver Code
let nums=[12, 11, 13, 5, 6, 7 ];
mergeSort(nums, 0, nums.length - 1);
document.write((nums).join(" "));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
5 6 7 11 12 13
Complejidad del tiempo: O(log n*nlog n)
Nota: el método mergeSort hace log n llamadas recursivas y cada vez que se llama a merge, lo que lleva n log n tiempo para fusionar 2 subarreglos ordenados
Enfoque 3: Aquí usamos la siguiente técnica:
Suppose we have a number A and we want to convert it to a number B and there is also a constraint that we can recover number A any time without using other variable.To achieve this we choose a number N which is greater than both numbers and add B*N in A. so A --> A+B*N To get number B out of (A+B*N) we divide (A+B*N) by N (A+B*N)/N = B. To get number A out of (A+B*N) we take modulo with N (A+B*N)%N = A. -> In short by taking modulo we get old number back and taking divide we new number.
mergeSort():
- Calcule mid two divida la array en dos mitades (sub-array izquierda y sub-array derecha)
- Llame recursivamente a la ordenación por combinación en el subconjunto izquierdo y el subconjunto derecho para ordenarlos
- Llame a la función de fusión para fusionar el subconjunto izquierdo y el subconjunto derecho
unir():
- Primero encontramos el elemento máximo de ambos subconjuntos y lo incrementamos en uno para evitar la colisión de 0 y el elemento máximo durante la operación de módulo.
- La idea es atravesar ambos sub-arreglos desde el inicio simultáneamente. Uno comienza desde l hasta m y otro comienza desde m+1 hasta r. Entonces, inicializaremos 3 punteros, digamos i, j, k.
- me moveré de l a m; j se moverá desde m+1 hasta r; k se moverá de l a r.
- Ahora actualice el valor a[k] agregando min(a[i],a[j])*maximum_element.
- Luego, actualice también los elementos que quedan en ambos subconjuntos.
- Después de actualizar todos los elementos, divida todos los elementos por max_element para recuperar la array actualizada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program in-place Merge Sort
#include <bits/stdc++.h>
using namespace std;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
void mergeInPlace(int a[], int l, int m, int r)
{
// increment the maximum_element by one to avoid
// collision of 0 and maximum element of array in modulo
// operation
int mx = max(a[m], a[r]) + 1;
int i = l, j = m + 1, k = l;
while (i <= m && j <= r && k <= r) {
// recover back original element to compare
int e1 = a[i] % mx;
int e2 = a[j] % mx;
if (e1 <= e2) {
a[k] += (e1 * mx);
i++;
k++;
}
else {
a[k] += (e2 * mx);
j++;
k++;
}
}
// process those elements which are left in the array
while (i <= m) {
int el = a[i] % mx;
a[k] += (el * mx);
i++;
k++;
}
while (j <= r) {
int el = a[j] % mx;
a[k] += (el * mx);
j++;
k++;
}
// finally update elements by dividing with maximum
// element
for (int i = l; i <= r; i++)
a[i] /= mx;
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
mergeInPlace(arr, l, m, r);
}
}
// Driver Code
int main()
{
int nums[] = { 12, 11, 13, 5, 6, 7 };
int nums_size = sizeof(nums) / sizeof(nums[0]);
mergeSort(nums, 0, nums_size - 1);
for (int i = 0; i < nums_size; i++) {
cout << nums[i] << " ";
}
return 0;
}
// This code is contributed by soham11806959
Java
// Java program in-place Merge Sort
import java.io.*;
import java.util.*;
class GFG {
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
private static void mergeInPlace(int a[], int l, int m, int r)
{
// increment the maximum_element by one to avoid
// collision of 0 and maximum element of array in modulo
// operation
int mx = Math.max(a[m], a[r]) + 1;
int i = l, j = m + 1, k = l;
while (i <= m && j <= r && k <= r) {
// recover back original element to compare
int e1 = a[i] % mx;
int e2 = a[j] % mx;
if (e1 <= e2) {
a[k] += (e1 * mx);
i++;
k++;
}
else {
a[k] += (e2 * mx);
j++;
k++;
}
}
// process those elements which are left in the array
while (i <= m) {
int el = a[i] % mx;
a[k] += (el * mx);
i++;
k++;
}
while (j <= r) {
int el = a[j] % mx;
a[k] += (el * mx);
j++;
k++;
}
// finally update elements by dividing with maximum
// element
for (i = l; i <= r; i++)
a[i] /= mx;
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
private static void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l + r) / 2, but avoids overflow
// for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
mergeInPlace(arr, l, m, r);
}
}
// Driver Code
public static void main(String[] args)
{
int nums[] = { 12, 11, 13, 5, 6, 7 };
int nums_size = nums.length;
mergeSort(nums, 0, nums_size - 1);
for (int i = 0; i < nums_size; i++) {
System.out.print(nums[i]+" ");
}
}
}
// This code is contributed by Pushpesh Raj
Producción
5 6 7 11 12 13
Complejidad de tiempo: O(n log n)
Nota: La complejidad de tiempo del enfoque anterior es O(n2) porque la combinación es O(n). La complejidad temporal de la ordenación por fusión estándar es O(n log n).
Enfoque 4 : aquí usamos la siguiente técnica para realizar una combinación en el lugar
Given 2 adjacent sorted sub-arrays within an array (hereafter named A and B for convenience), appreciate that we can swap some of the last portion of A with an equal number of elements from the start of B, such that after the exchange, all of the elements in A are less than or equal to any element in B. After this exchange, this leaves with the A containing 2 sorted sub-arrays, being the first original portion of A, and the first original portion of B, and sub-array B now containing 2 sorted sub-arrays, being the final original portion of A followed by the final original portion of B We can now recursively call the merge operation with the 2 sub-arrays of A, followed by recursively calling the merge operation with the 2 sub-arrays of B We stop the recursion when either A or B are empty, or when either sub-array is small enough to efficiently merge into the other sub-array using insertion sort.
El procedimiento anterior, naturalmente, se presta a la siguiente implementación de una clasificación de combinación en el lugar.
unir():
- De aquí en adelante, por conveniencia, nos referiremos al primer subconjunto como A y al segundo subconjunto como B.
- Si A o B están vacíos, o si el primer elemento B no es menor que el último elemento de A, entonces hemos terminado.
- Si la longitud de A es lo suficientemente pequeña y si su longitud es menor que la longitud de B, utilice la ordenación por inserción para fusionar A en B y devolver
- Si la longitud de B es lo suficientemente pequeña, use la ordenación por inserción para fusionar B en A y devolver
- Encuentre la ubicación en A donde podemos intercambiar la porción restante de A con la primera porción de B, de modo que todos los elementos en A sean menores o iguales que cualquier elemento en B
- Realizar el intercambio entre A y B
- Llame recursivamente a merge() en los 2 subarreglos ordenados que ahora residen en A
- Llame recursivamente a merge() en los 2 subarreglos ordenados que ahora residen en B
merge_sort():
- Divida la array en dos mitades (sub-array izquierda y sub-array derecha)
- Llame recursivamente a merge_sort() en el subconjunto izquierdo y el subconjunto derecho para ordenarlos
- Llame a la función de fusión para fusionar el subconjunto izquierdo y el subconjunto derecho
C++
// Merge In Place in C++
#include <iostream>
using namespace std;
#define __INSERT_THRESH 5
#define __swap(x, y) (t = *(x), *(x) = *(y), *(y) = t)
// Both sorted sub-arrays must be adjacent in 'a'
// 'an' is the length of the first sorted section in 'a'
// 'bn' is the length of the second sorted section in 'a'
static void merge(int* a, size_t an, size_t bn)
{
int *b = a + an, *e = b + bn, *s, t;
// Return right now if we're done
if (an == 0 || bn == 0 || !(*b < *(b - 1)))
return;
// Do insertion sort to merge if size of sub-arrays are
// small enough
if (an < __INSERT_THRESH && an <= bn) {
for (int *p = b, *v; p > a;
p--) // Insert Sort A into B
for (v = p, s = p - 1; v < e && *v < *s;
s = v, v++)
__swap(s, v);
return;
}
if (bn < __INSERT_THRESH) {
for (int *p = b, *v; p < e;
p++) // Insert Sort B into A
for (s = p, v = p - 1; s > a && *s < *v;
s = v, v--)
__swap(s, v);
return;
}
// Find the pivot points. Basically this is just
// finding the point in 'a' where we can swap in the
// first part of 'b' such that after the swap the last
// element in 'a' will be less than or equal to the
// least element in 'b'
int *pa = a, *pb = b;
for (s = a; s < b && pb < e; s++)
if (*pb < *pa)
pb++;
else
pa++;
pa += b - s;
// Swap first part of b with last part of a
for (int *la = pa, *fb = b; la < b; la++, fb++)
__swap(la, fb);
// Now merge the two sub-array pairings
merge(a, pa - a, pb - b);
merge(b, pb - b, e - pb);
} // merge_array_inplace
#undef __swap
#undef __INSERT_THRESH
// Merge Sort Implementation
void merge_sort(int* a, size_t n)
{
size_t m = (n + 1) / 2;
// Sort first and second halves
if (m > 1)
merge_sort(a, m);
if (n - m > 1)
merge_sort(a + m, n - m);
// Now merge the two sorted sub-arrays together
merge(a, m, n - m);
}
// Function to print an array
void print_array(int a[], size_t n)
{
if (n > 0) {
cout <<" "<< a[0];
for (size_t i = 1; i < n; i++)
cout <<" "<< a[i];
}
cout <<"\n";
}
// Driver program to test sort utility
int main()
{
int a[] = { 3, 16, 5, 14, 8, 10, 7, 15,
1, 13, 4, 9, 12, 11, 6, 2 };
size_t n = sizeof(a) / sizeof(a[0]);
merge_sort(a, n);
print_array(a, n);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// Merge In Place in C
#include <stddef.h>
#include <stdio.h>
#define __INSERT_THRESH 5
#define __swap(x, y) (t = *(x), *(x) = *(y), *(y) = t)
// Both sorted sub-arrays must be adjacent in 'a'
// 'an' is the length of the first sorted section in 'a'
// 'bn' is the length of the second sorted section in 'a'
static void merge(int* a, size_t an, size_t bn)
{
int *b = a + an, *e = b + bn, *s, t;
// Return right now if we're done
if (an == 0 || bn == 0 || !(*b < *(b - 1)))
return;
// Do insertion sort to merge if size of sub-arrays are
// small enough
if (an < __INSERT_THRESH && an <= bn) {
for (int *p = b, *v; p > a;
p--) // Insert Sort A into B
for (v = p, s = p - 1; v < e && *v < *s;
s = v, v++)
__swap(s, v);
return;
}
if (bn < __INSERT_THRESH) {
for (int *p = b, *v; p < e;
p++) // Insert Sort B into A
for (s = p, v = p - 1; s > a && *s < *v;
s = v, v--)
__swap(s, v);
return;
}
// Find the pivot points. Basically this is just
// finding the point in 'a' where we can swap in the
// first part of 'b' such that after the swap the last
// element in 'a' will be less than or equal to the
// least element in 'b'
int *pa = a, *pb = b;
for (s = a; s < b && pb < e; s++)
if (*pb < *pa)
pb++;
else
pa++;
pa += b - s;
// Swap first part of b with last part of a
for (int *la = pa, *fb = b; la < b; la++, fb++)
__swap(la, fb);
// Now merge the two sub-array pairings
merge(a, pa - a, pb - b);
merge(b, pb - b, e - pb);
} // merge_array_inplace
#undef __swap
#undef __INSERT_THRESH
// Merge Sort Implementation
void merge_sort(int* a, size_t n)
{
size_t m = (n + 1) / 2;
// Sort first and second halves
if (m > 1)
merge_sort(a, m);
if (n - m > 1)
merge_sort(a + m, n - m);
// Now merge the two sorted sub-arrays together
merge(a, m, n - m);
}
// Function to print an array
void print_array(int a[], size_t n)
{
if (n > 0) {
printf("%d", a[0]);
for (size_t i = 1; i < n; i++)
printf(" %d", a[i]);
}
printf("\n");
}
// Driver program to test sort utiliyy
int main()
{
int a[] = { 3, 16, 5, 14, 8, 10, 7, 15,
1, 13, 4, 9, 12, 11, 6, 2 };
size_t n = sizeof(a) / sizeof(a[0]);
merge_sort(a, n);
print_array(a, n);
return 0;
}
// Author: Stew Forster (stew675@gmail.com) Date: 29
// July 2021
Producción
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Complejidad de tiempo de merge() : Peor caso: O(n^2), Promedio: O(n log n), Mejor: O(1)
Complejidad temporal de la función merge_sort(): En general: O(log n) solo para la recursividad, debido a que siempre se divide uniformemente la array en 2
Complejidad temporal de merge_sort() en general: Peor caso: O(n^2 log n), Promedio: O(n (log n)^2), Mejor: O(log n)
El peor de los casos ocurre cuando cada intercambio de subarreglo dentro de merge() da como resultado que solo se intercambien _INSERT_THRESH-1 elementos