Dada una array de enteros de la que se ordenan tanto la primera mitad como la segunda mitad. La tarea es fusionar dos mitades ordenadas de una array en una sola array ordenada.
Ejemplos:
Input : A[] = { 2, 3, 8, -1, 7, 10 }
Output : -1, 2, 3, 7, 8, 10
Input : A[] = {-4, 6, 9, -1, 3 }
Output : -4, -1, 3, 6, 9
Método 1: una solución simple es ordenar la array usando funciones integradas (generalmente una implementación de ordenación rápida).
A continuación se muestra la implementación del método anterior:
C++
// C++ program to Merge two sorted halves of
// array Into Single Sorted Array
#include <bits/stdc++.h>
using namespace std;
void mergeTwoHalf(int A[], int n)
{
// Sort the given array using sort STL
sort(A, A + n);
}
// Driver code
int main()
{
int A[] = { 2, 3, 8, -1, 7, 10 };
int n = sizeof(A) / sizeof(A[0]);
mergeTwoHalf(A, n);
// Print sorted Array
for (int i = 0; i < n; i++)
cout << A[i] << " ";
return 0;
}
Java
// Java program to Merge two sorted halves of
// array Into Single Sorted Array
import java.io.*;
import java.util.*;
class GFG {
static void mergeTwoHalf(int[] A, int n)
{
// Sort the given array using sort STL
Arrays.sort(A);
}
// Driver code
static public void main(String[] args)
{
int[] A = { 2, 3, 8, -1, 7, 10 };
int n = A.length;
mergeTwoHalf(A, n);
// Print sorted Array
for (int i = 0; i < n; i++)
System.out.print(A[i] + " ");
}
}
// This code is contributed by vt_m .
Python3
# Python program to Merge two sorted # halves of array Into Single Sorted Array def mergeTwoHalf(A, n): # Sort the given array using sort STL A.sort() # Driver Code if __name__ == '__main__': A = [2, 3, 8, -1, 7, 10] n = len(A) mergeTwoHalf(A, n) # Print sorted Array for i in range(n): print(A[i], end=" ") # This code is contributed by 29AjayKumar
C#
// C# program to Merge two sorted halves of
// array Into Single Sorted Array
using System;
class GFG {
static void mergeTwoHalf(int[] A, int n)
{
// Sort the given array using sort STL
Array.Sort(A);
}
// Driver code
static public void Main()
{
int[] A = { 2, 3, 8, -1, 7, 10 };
int n = A.Length;
mergeTwoHalf(A, n);
// Print sorted Array
for (int i = 0; i < n; i++)
Console.Write(A[i] + " ");
}
}
// This code is contributed by vt_m .
PHP
<?php
// PHP program to Merge two sorted halves
// of array Into Single Sorted Array
function mergeTwoHalf(&$A, $n)
{
// Sort the given array using sort STL
sort($A, 0);
}
// Driver Code
$A = array(2, 3, 8, -1, 7, 10);
$n = sizeof($A);
mergeTwoHalf($A, $n);
// Print sorted Array
for ($i = 0; $i < $n; $i++)
echo $A[$i] . " ";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to Merge two sorted halves of
// array Into Single Sorted Array
function mergeTwoHalf(A, n)
{
// Sort the given array using sort function
A.sort((a,b) => a-b);
}
// Driver code
var A = [ 2, 3, 8, -1, 7, 10 ];
var n = A.length;
mergeTwoHalf(A, n);
// Print sorted Array
for (var i = 0; i < n; i++)
document.write( A[i] + " ");
// This code is contributed by itsok.
</script>
Producción
-1 2 3 7 8 10
Complejidad del tiempo:
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
caso mejor y promedio, 
peor caso (para clasificación rápida)
Complejidad espacial:
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
a
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
dependiendo del caso y la implementación (para quicksort)
Para obtener más detalles, consulte el artículo de GFG sobre Quicksort.
Método 2: una solución más eficiente es usar una array auxiliar que es muy similar a la función Merge de Merge sort .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Merge Two Sorted Halves Of
// Array Into Single Sorted Array
#include <bits/stdc++.h>
using namespace std;
// Merge two sorted halves of Array into single
// sorted array
void mergeTwoHalf(int A[], int n)
{
int half_i = 0; // starting index of second half
// Temp Array store sorted resultant array
int temp[n];
// First Find the point where array is divide
// into two half
for (int i = 0; i < n - 1; i++) {
if (A[i] > A[i + 1]) {
half_i = i + 1;
break;
}
}
// If Given array is all-ready sorted
if (half_i == 0)
return;
// Merge two sorted arrays in single sorted array
int i = 0, j = half_i, k = 0;
while (i < half_i && j < n) {
if (A[i] < A[j])
temp[k++] = A[i++];
else
temp[k++] = A[j++];
}
// Copy the remaining elements of A[i to half_! ]
while (i < half_i)
temp[k++] = A[i++];
// Copy the remaining elements of A[ half_! to n ]
while (j < n)
temp[k++] = A[j++];
for (int i = 0; i < n; i++)
A[i] = temp[i];
}
// Driver code
int main()
{
int A[] = { 2, 3, 8, -1, 7, 10 };
int n = sizeof(A) / sizeof(A[0]);
mergeTwoHalf(A, n);
// Print sorted Array
for (int i = 0; i < n; i++)
cout << A[i] << " ";
return 0;
}
Java
// Java program to Merge Two Sorted Halves Of
// Array Into Single Sorted Array
import java.io.*;
class GFG {
// Merge two sorted halves of Array
// into single sorted array
static void mergeTwoHalf(int[] A, int n)
{
int half_i = 0; // starting index of second half
int i;
// Temp Array store sorted resultant array
int[] temp = new int[n];
// First Find the point where array is divide
// into two half
for (i = 0; i < n - 1; i++) {
if (A[i] > A[i + 1]) {
half_i = i + 1;
break;
}
}
// If Given array is all-ready sorted
if (half_i == 0)
return;
// Merge two sorted arrays in single sorted array
i = 0;
int j = half_i;
int k = 0;
while (i < half_i && j < n) {
if (A[i] < A[j])
temp[k++] = A[i++];
else
temp[k++] = A[j++];
}
// Copy the remaining elements of A[i to half_! ]
while (i < half_i)
temp[k++] = A[i++];
// Copy the remaining elements of A[ half_! to n ]
while (j < n)
temp[k++] = A[j++];
for (i = 0; i < n; i++)
A[i] = temp[i];
}
// Driver code
static public void main(String[] args)
{
int[] A = { 2, 3, 8, -1, 7, 10 };
int n = A.length;
mergeTwoHalf(A, n);
// Print sorted Array
for (int i = 0; i < n; i++)
System.out.print(A[i] + " ");
}
}
// This code is contributed by vt_m .
Python3
# Python3 program to Merge Two Sorted Halves Of # Array Into Single Sorted Array # Merge two sorted halves of Array into single # sorted array def mergeTwoHalf(A, n): # Starting index of second half half_i = 0 # Temp Array store sorted resultant array temp = [0 for i in range(n)] # First Find the point where array is # divide into two half for i in range(n - 1): if (A[i] > A[i + 1]): half_i = i + 1 break # If Given array is all-ready sorted if (half_i == 0): return # Merge two sorted arrays in single # sorted array i = 0 j = half_i k = 0 while (i < half_i and j < n): if (A[i] < A[j]): temp[k] = A[i] k += 1 i += 1 else: temp[k] = A[j] k += 1 j += 1 # Copy the remaining elements of A[i to half_! ] while i < half_i: temp[k] = A[i] k += 1 i += 1 # Copy the remaining elements of A[ half_! to n ] while (j < n): temp[k] = A[j] k += 1 j += 1 for i in range(n): A[i] = temp[i] # Driver code A = [ 2, 3, 8, -1, 7, 10 ] n = len(A) mergeTwoHalf(A, n) # Print sorted Array print(*A, sep = ' ') # This code is contributed by avanitrachhadiya2155
C#
// C# program to Merge Two Sorted Halves Of
// Array Into Single Sorted Array
using System
class GFG {
// Merge two sorted halves of Array
// into single sorted array
static void mergeTwoHalf(int[] A, int n)
{
int half_i = 0
// starting index of second half
int i
// Temp Array store sorted resultant array
int[] temp
= new int[n]
// First Find the point where array is divide
// into two half
for (i = 0 i < n - 1 i++)
{
if (A[i] > A[i + 1]) {
half_i = i + 1 break
}
}
// If Given array is all-ready sorted
if (half_i == 0)
return
// Merge two sorted arrays in single sorted
// array
i = 0 int j = half_i int k
= 0 while (i < half_i & &j < n)
{
if (A[i] < A[j])
temp[k++] = A[i++] else temp[k++]
= A[j++]
}
// Copy the remaining elements of A[i to half_!]
while (i < half_i)
temp[k++] = A[i++]
// Copy the remaining elements of A[half_!
// to n]
while (j < n) temp[k++]
= A[j++]
for (i = 0 i < n i++) A[i]
= temp[i]
}
// Driver code
static public void Main()
{
int[] A
= { 2,
3,
8,
-1,
7,
10 } int n
= A.Length mergeTwoHalf(A, n)
// Print sorted Array
for (int i = 0 i < n i++)
Console.Write(A[i] + " ")
}
}
// This code is contributed by vt_m .
Javascript
<script>
// JavaScript program to Merge Two Sorted Halves Of
// Array Into Single Sorted Array
// Merge two sorted halves of Array into single
// sorted array
function mergeTwoHalf(A, n)
{
let half_i = 0; // starting index of second half
// Temp Array store sorted resultant array
let temp = new Array(n);
temp.fill(0);
// First Find the point where array is divide
// into two half
for (let i = 0; i < n - 1; i++) {
if (A[i] > A[i + 1]) {
half_i = i + 1;
break;
}
}
// If Given array is all-ready sorted
if (half_i == 0)
return;
// Merge two sorted arrays in single sorted array
let i = 0, j = half_i, k = 0;
while (i < half_i && j < n) {
if (A[i] < A[j])
temp[k++] = A[i++];
else
temp[k++] = A[j++];
}
// Copy the remaining elements of A[i to half_! ]
while (i < half_i)
temp[k++] = A[i++];
// Copy the remaining elements of A[ half_! to n ]
while (j < n)
temp[k++] = A[j++];
for (let i = 0; i < n; i++)
A[i] = temp[i];
}
let A = [ 2, 3, 8, -1, 7, 10 ];
let n = A.length;
mergeTwoHalf(A, n);
// Print sorted Array
for (let i = 0; i < n; i++)
document.write(A[i] + " ");
</script>
Producción
-1 2 3 7 8 10
Complejidad del tiempo:
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
Complejidad espacial:
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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