Tutorialspoint.dev

Sort an array when two halves are sorted

Given an integer array of which both first half and second half are sorted. Task is to merge two sorted halves of array into single sorted array.

Examples:

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 



A Simple Solution is to sort the array.
Below is the implementation of above approach :

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 program to test above function
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 program to test above function
    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 .

/div>

Python3

# Python3 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 program to test above function
    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
?>


Output:

-1 2 3 7 8 10  

Time Complexity O(nlogn) || Sort Given array using quick sort or merge sort

An efficient solution is to use an auxiliary array one half. Now whole process is same as the Merge Function of Merge sort.
Below is the implementation of above approach :

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 program to test above function
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 program to test above function
    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 .

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 program to test above function
    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 .


Output:

-1 2 3 7 8 10 

Time Complexity : O(n)

Reference : https://www.careercup.com/question?id=8412257

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter