A continuación se muestra una implementación recursiva típica de Merge Sort
C++
// Recursive C++ program for merge sort
#include<bits/stdc++.h>
using namespace std;
// Function to merge the two haves
// arr[l..m] and arr[m+1..r] of array arr[]
void merge(int arr[], int l, int m, int r);
// 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 & h
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Function to merge the two haves arr[l..m]
// and arr[m+1..r] of array arr[]
void merge(int arr[], int l, int m, int r)
{
int k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
// Copy data to temp arrays L[] and R[]
for(int i = 0; i < n1; i++)
L[i] = arr[l + i];
for(int j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
// Merge the temp arrays
// back into arr[l..r]
int i = 0;
int j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements
// of L[], if there are any
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements
// of R[], if there are any
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Function to print an array
void printArray(int A[], int size)
{
for(int i = 0; i < size; i++)
printf("%d ", A[i]);
cout << "\n";
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
// This code is contributed by Mayank Tyagi
C
/* Recursive C program for merge sort */
#include<stdlib.h>
#include<stdio.h>
/* Function to merge the two haves
arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r);
/* 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 & h
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* Function to merge the two haves arr[l..m]
and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements
of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements
of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* 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]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
Java
// Recursive Java Program for merge sort
import java.util.Arrays;
public class GFG
{
public static void mergeSort(int[] array)
{
if(array == null)
{
return;
}
if(array.length > 1)
{
int mid = array.length / 2;
// Split left part
int[] left = new int[mid];
for(int i = 0; i < mid; i++)
{
left[i] = array[i];
}
// Split right part
int[] right = new int[array.length - mid];
for(int i = mid; i < array.length; i++)
{
right[i - mid] = array[i];
}
mergeSort(left);
mergeSort(right);
int i = 0;
int j = 0;
int k = 0;
// Merge left and right arrays
while(i < left.length && j < right.length)
{
if(left[i] < right[j])
{
array[k] = left[i];
i++;
}
else
{
array[k] = right[j];
j++;
}
k++;
}
// Collect remaining elements
while(i < left.length)
{
array[k] = left[i];
i++;
k++;
}
while(j < right.length)
{
array[k] = right[j];
j++;
k++;
}
}
}
// Driver program to test above functions.
public static void main(String[] args)
{
int arr[] = {12, 11, 13, 5, 6, 7};
int i=0;
System.out.println("Given array is");
for(i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
mergeSort(arr);
System.out.println("\n");
System.out.println("Sorted array is");
for(i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
}
// Code Contributed by Mohit Gupta_OMG
Python3
# Recursive Python Program for merge sort
def merge(left, right):
if not len(left) or not len(right):
return left or right
result = []
i, j = 0, 0
while (len(result) < len(left) + len(right)):
if left[i] < right[j]:
result.append(left[i])
i+= 1
else:
result.append(right[j])
j+= 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break
return result
def mergesort(list):
if len(list) < 2:
return list
middle = int(len(list)/2)
left = mergesort(list[:middle])
right = mergesort(list[middle:])
return merge(left, right)
seq = [12, 11, 13, 5, 6, 7]
print("Given array is")
print(seq);
print("\n")
print("Sorted array is")
print(mergesort(seq))
# Code Contributed by Mohit Gupta_OMG
C#
/* Iterative C# program for merge
sort */
using System;
class GFG {
/* 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 & h
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* Function to merge the two haves
arr[l..m] and arr[m+1..r] of array
arr[] */
static void merge(int[] arr, int l,
int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int []L = new int[n1];
int []R = new int[n2];
/* Copy data to temp arrays
L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back
into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of
L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of
R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* 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.Write("\n");
}
/* Driver program to test above functions */
public static void Main()
{
int []arr = {12, 11, 13, 5, 6, 7};
int arr_size = arr.Length;
Console.Write("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
Console.Write("\nSorted array is \n");
printArray(arr, arr_size);
}
}
// This code is contributed by Smitha
Javascript
<script>
// Recursive javascript Program for merge sort
function mergeSort(array) {
if (array == null) {
return;
}
if (array.length > 1) {
var mid = parseInt(array.length / 2);
// Split left part
var left = Array(mid).fill(0);
for (i = 0; i < mid; i++) {
left[i] = array[i];
}
// Split right part
var right = Array(array.length - mid).fill(0);
for (i = mid; i < array.length; i++) {
right[i - mid] = array[i];
}
mergeSort(left);
mergeSort(right);
var i = 0;
var j = 0;
var k = 0;
// Merge left and right arrays
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
array[k] = left[i];
i++;
} else {
array[k] = right[j];
j++;
}
k++;
}
// Collect remaining elements
while (i < left.length) {
array[k] = left[i];
i++;
k++;
}
while (j < right.length) {
array[k] = right[j];
j++;
k++;
}
}
}
// Driver program to test above functions.
var arr = [ 12, 11, 13, 5, 6, 7 ];
var i = 0;
document.write("Given array is<br/>");
for (i = 0; i < arr.length; i++)
document.write(arr[i] + " ");
mergeSort(arr);
document.write("<br/><br/>");
document.write("Sorted array is<br/>");
for (i = 0; i < arr.length; i++)
document.write(arr[i] + " ");
// This code is contributed by umadevi9616
</script>
Producción:
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
Clasificación de combinación iterativa:
la función anterior es recursiva, por lo que utiliza la pila de llamadas de función para almacenar valores intermedios de l y h. La pila de llamadas de función almacena otra información de contabilidad junto con parámetros. Además, las llamadas a funciones implican gastos generales como almacenar el registro de activación de la función que llama y luego reanudar la ejecución. A diferencia de Iterative QuickSort , iterative MergeSort no requiere una pila auxiliar explícita.
Nota: En la ordenación de combinación iterativa, hacemos un enfoque de abajo hacia arriba, es decir, comenzamos desde una array del tamaño de 2 elementos (sabemos que la array del tamaño de 1 elemento ya está ordenada). Además, el punto clave es que, dado que no sabemos cómo dividir la array exactamente como en el enfoque de arriba hacia abajo, donde la array de tamaño de 2 elementos puede tener una secuencia de tamaño 2,1,2,2,1… nosotros en el enfoque de abajo hacia arriba suponga que la array se dividió exactamente por potencias de 2 (n/2,n/4… etc.) para un tamaño de array de potencias de 2, por ejemplo: n=2,4,8,16.
Entonces, para otros tamaños de entrada como 5, 7, 11, tendremos una sublista restante que no entró en la potencia de 2 anchos en cada nivel a medida que continuamos fusionándonos y subiendo, esta sublista no fusionada que es de tamaño que no es potencia exacta de 2, permanecerá aislado hasta la fusión final.
Para fusionar esta lista no fusionada en la fusión final, debemos forzar que el medio esté al comienzo de la lista no fusionada para que sea un candidato para la fusión.
El recuento de elementos de la sublista no fusionados que se aislará hasta la llamada de fusión final se puede averiguar utilizando el resto (n % de ancho). La fusión final (cuando tenemos listas desiguales) se puede identificar por (ancho>n/2).
Dado que el ancho crece en potencias de 2 cuando el ancho == n/2, significa que la entrada ya tenía un tamaño en potencias de 2, de lo contrario, si el ancho < n/2, aún no hemos llegado a la fusión final, entonces cuando el ancho > n /2 debemos tener una lista desigual no fusionada pendiente, por lo tanto, reiniciamos mid solo en tal caso.
La función anterior se puede convertir fácilmente a una versión iterativa. A continuación se muestra una ordenación de combinación iterativa.
C++
/* Iterative C program for merge sort */
#include <bits/stdc++.h>
using namespace std;
/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r);
// Utility function to find minimum of two integers
int min(int x, int y) { return (x<y)? x :y; }
/* Iterative mergesort function to sort arr[0...n-1] */
void mergeSort(int arr[], int n)
{
int curr_size; // For current size of subarrays to be merged
// curr_size varies from 1 to n/2
int left_start; // For picking starting index of left subarray
// to be merged
// Merge subarrays in bottom up manner. First merge subarrays of
// size 1 to create sorted subarrays of size 2, then merge subarrays
// of size 2 to create sorted subarrays of size 4, and so on.
for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
{
// Pick starting point of different subarrays of current size
for (left_start=0; left_start<n-1; left_start += 2*curr_size)
{
// Find ending point of left subarray. mid+1 is starting
// point of right
int mid = min(left_start + curr_size - 1, n-1);
int right_end = min(left_start + 2*curr_size - 1, n-1);
// Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}
/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* 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 n = sizeof(arr)/sizeof(arr[0]);
cout <<"Given array is \n ";
printArray(arr, n);
mergeSort(arr, n);
cout <<"\nSorted array is \n ";
printArray(arr, n);
return 0;
}
// This code is contributed shivanisinghss2110
C
/* Iterative C program for merge sort */
#include<stdlib.h>
#include<stdio.h>
/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r);
// Utility function to find minimum of two integers
int min(int x, int y) { return (x<y)? x :y; }
/* Iterative mergesort function to sort arr[0...n-1] */
void mergeSort(int arr[], int n)
{
int curr_size; // For current size of subarrays to be merged
// curr_size varies from 1 to n/2
int left_start; // For picking starting index of left subarray
// to be merged
// Merge subarrays in bottom up manner. First merge subarrays of
// size 1 to create sorted subarrays of size 2, then merge subarrays
// of size 2 to create sorted subarrays of size 4, and so on.
for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
{
// Pick starting point of different subarrays of current size
for (left_start=0; left_start<n-1; left_start += 2*curr_size)
{
// Find ending point of left subarray. mid+1 is starting
// point of right
int mid = min(left_start + curr_size - 1, n-1);
int right_end = min(left_start + 2*curr_size - 1, n-1);
// Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}
/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* 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 n = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, n);
mergeSort(arr, n);
printf("\nSorted array is \n");
printArray(arr, n);
return 0;
}
Java
/* Iterative Java program for merge sort */
import java.lang.Math.*;
class GFG {
/* Iterative mergesort function to sor
t arr[0...n-1] */
static void mergeSort(int arr[], int n)
{
// For current size of subarrays to
// be merged curr_size varies from
// 1 to n/2
int curr_size;
// For picking starting index of
// left subarray to be merged
int left_start;
// Merge subarrays in bottom up
// manner. First merge subarrays
// of size 1 to create sorted
// subarrays of size 2, then merge
// subarrays of size 2 to create
// sorted subarrays of size 4, and
// so on.
for (curr_size = 1; curr_size <= n-1;
curr_size = 2*curr_size)
{
// Pick starting point of different
// subarrays of current size
for (left_start = 0; left_start < n-1;
left_start += 2*curr_size)
{
// Find ending point of left
// subarray. mid+1 is starting
// point of right
int mid = Math.min(left_start + curr_size - 1, n-1);
int right_end = Math.min(left_start
+ 2*curr_size - 1, n-1);
// Merge Subarrays arr[left_start...mid]
// & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}
/* Function to merge the two haves arr[l..m] and
arr[m+1..r] of array arr[] */
static void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/* Copy data to temp arrays L[]
and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into
arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of
L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of
R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* Function to print an array */
static void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
System.out.printf("%d ", A[i]);
System.out.printf("\n");
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
System.out.printf("Given array is \n");
printArray(arr, n);
mergeSort(arr, n);
System.out.printf("\nSorted array is \n");
printArray(arr, n);
}
}
// This code is contributed by Smitha
Python3
# Iterative Merge sort (Bottom Up)
# Iterative mergesort function to
# sort arr[0...n-1]
# perform bottom up merge
def mergeSort(a):
# start with least partition size of 2^0 = 1
width = 1
n = len(a)
# subarray size grows by powers of 2
# since growth of loop condition is exponential,
# time consumed is logarithmic (log2n)
while (width < n):
# always start from leftmost
l=0;
while (l < n):
r = min(l+(width*2-1), n-1)
m = min(l+width-1,n-1)
# final merge should consider
# unmerged sublist if input arr
# size is not power of 2
merge(a, l, m, r)
l += width*2
# Increasing sub array size by powers of 2
width *= 2
return a
# Merge Function
def merge(a, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * n1
R = [0] * n2
for i in range(0, n1):
L[i] = a[l + i]
for i in range(0, n2):
R[i] = a[m + i + 1]
i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] <= R[j]:
a[k] = L[i]
i += 1
else:
a[k] = R[j]
j += 1
k += 1
while i < n1:
a[k] = L[i]
i += 1
k += 1
while j < n2:
a[k] = R[j]
j += 1
k += 1
# Driver code
a = [-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39]
print("Given array is ")
print(a)
mergeSort(a)
print("Sorted array is ")
print(a)
# Contributed by Madhur Chhangani [RCOEM]
# corrected and improved by @mahee96
C#
/* Iterative C# program for merge sort */
using System;
public class GFG {
/* Iterative mergesort function to sor
t arr[0...n-1] */
static void mergeSort(int []arr, int n)
{
// For current size of subarrays to
// be merged curr_size varies from
// 1 to n/2
int curr_size;
// For picking starting index of
// left subarray to be merged
int left_start;
// Merge subarrays in bottom up
// manner. First merge subarrays
// of size 1 to create sorted
// subarrays of size 2, then merge
// subarrays of size 2 to create
// sorted subarrays of size 4, and
// so on.
for (curr_size = 1; curr_size <= n-1;
curr_size = 2*curr_size)
{
// Pick starting point of different
// subarrays of current size
for (left_start = 0; left_start < n-1;
left_start += 2*curr_size)
{
// Find ending point of left
// subarray. mid+1 is starting
// point of right
int mid = Math.Min(left_start + curr_size - 1,n-1);
int right_end = Math.Min(left_start
+ 2*curr_size - 1, n-1);
// Merge Subarrays arr[left_start...mid]
// & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}
/* Function to merge the two haves arr[l..m] and
arr[m+1..r] of array arr[] */
static void merge(int []arr, int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int []L = new int[n1];
int []R = new int[n2];
/* Copy data to temp arrays L[]
and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into
arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of
L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of
R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* 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 program to test above functions */
public static void Main()
{
int []arr = {-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39};
int n = arr.Length;
Console.Write("Given array is \n");
printArray(arr, n);
mergeSort(arr, n);
Console.Write("\nSorted array is \n");
printArray(arr, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
/* Iterative javascript program for merge sort */
/*
* Iterative mergesort function to sor t arr[0...n-1]
*/
function mergeSort(arr , n) {
// For current size of subarrays to
// be merged curr_size varies from
// 1 to n/2
var curr_size;
// For picking starting index of
// left subarray to be merged
var left_start;
// Merge subarrays in bottom up
// manner. First merge subarrays
// of size 1 to create sorted
// subarrays of size 2, then merge
// subarrays of size 2 to create
// sorted subarrays of size 4, and
// so on.
for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) {
// Pick starting point of different
// subarrays of current size
for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
// Find ending point of left
// subarray. mid+1 is starting
// point of right
var mid = Math.min(left_start + curr_size - 1, n - 1);
var right_end = Math.min(left_start + 2 * curr_size - 1, n - 1);
// Merge Subarrays arr[left_start...mid]
// & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}
/*
* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr
*/
function merge(arr , l , m , r) {
var i, j, k;
var n1 = m - l + 1;
var n2 = r - m;
/* create temp arrays */
var L = Array(n1).fill(0);
var R = Array(n2).fill(0);
/*
* Copy data to temp arrays L and R
*/
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/*
* Merge the temp arrays back into arr[l..r]
*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
/*
* Copy the remaining elements of L, if there are any
*/
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/*
* Copy the remaining elements of R, if there are any
*/
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/* Function to print an array */
function printArray(A , size) {
var i;
for (i = 0; i < size; i++)
document.write( A[i]+" ");
document.write("<br/>");
}
/* Driver program to test above functions */
var arr = [-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39];
var n = arr.length;
document.write("Given array is <br/>");
printArray(arr, n);
mergeSort(arr, n);
document.write("<br/>Sorted array is <br/>");
printArray(arr, n);
// This code contributed by umadevi9616
</script>
Producción:
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
La complejidad temporal de la función iterativa anterior es la misma que la recursiva, es decir, Θ(nLogn).
Echa un vistazo al curso de autoaprendizaje de DSA
Referencias:
http://csg.sph.umich.edu/abecasis/class/2006/615.09.pdf
Este artículo es una contribución de Shivam Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA