Sort an array having first N elements sorted and last M elements are unsorted

Last Updated : 23 Jul, 2025

Given two positive integers, N and M, and an array arr[ ] consisting of (N + M) integers such that the first N elements are sorted in ascending order and the last M elements are unsorted, the task is to sort the given array in ascending order.

Examples:

Input: N = 3, M = 5, arr[] = {2, 8, 10, 17, 15, 23, 4, 12}
Output: 2 4 8 10 12 15 17 23

Input: N = 4, M = 3, arr[] = {4, 7, 9, 11, 10, 5, 17}
Output: 4 5 7 9 10 11 17

Naive Approach: The simplest approach to solve the given problem is to use the inbuilt sort() function to sort the given array.

C++

// C++ code for the approach #include <iostream> #include <algorithm> using namespace std; // Driver Code int main() {  int arr[] = { 2, 8, 10, 17, 15,  23, 4, 12 };  int n = sizeof(arr) / sizeof(arr[0]);  // Sorting the array using inbuilt function  sort(arr, arr + n);  // Printing the sorted array  for(int i = 0; i < n; i++) {  cout << arr[i] << " ";  }  cout << endl;  return 0; }

Java

// Java code for the approach import java.util.Arrays; class GFG {  // Driver Code  public static void main(String[] args)  {  int[] arr = { 2, 8, 10, 17, 15, 23, 4, 12 };  int n = arr.length;  // Sorting the array using inbuilt function  Arrays.sort(arr);  // Printing the sorted array  for (int i = 0; i < n; i++) {  System.out.print(arr[i] + " ");  }  System.out.println();  } }

Python3

# Python3 code for the approach if __name__ == '__main__': # Defining the array arr = [2, 8, 10, 17, 15, 23, 4, 12] n = len(arr) # Sorting the array using inbuilt function arr.sort() # Printing the sorted array for i in range(n): print(arr[i], end=" ") print()

using System; using System.Linq; class Program {  static void Main(string[] args)  {  int[] arr = { 2, 8, 10, 17, 15, 23, 4, 12 };  int n = arr.Length;  // Sorting the array using inbuilt function  Array.Sort(arr);  // Printing the sorted array  for (int i = 0; i < n; i++) {  Console.Write(arr[i] + " ");  }  Console.WriteLine();  Console.ReadLine();  } } // This code is contributed by user_dtewbxkn77n

JavaScript

let arr = [2, 8, 10, 17, 15, 23, 4, 12]; let n = arr.length; // Sorting the array using inbuilt function arr.sort(function(a,b){return a - b}); // Printing the sorted array for (let i = 0; i < n; i++) { console.log(arr[i] + " "); } console.log(); // This code is contributed by shivhack999

Output

2 4 8 10 12 15 17 23

Time Complexity: O((N + M)log(N + M))
Auxiliary Space: O(1)

Efficient Approach: The above approach can also be optimized by using the idea of Merge Sort. The idea is to perform the merge sort operation on the last M array elements and then use the concept of merging two sorted arrays for the first N and the last M element of the array. Follow the steps below to solve the problem:

Perform the merge sort operation on the last M array elements using the approach discussed in this article.
After the above steps, the subarrays arr[1, N] and arr[N + 1, M] is sorted in ascending order.
Merge the two sorted subarrays arr[1, N] and arr[N + 1, M] using the approach discussed in this article.
After completing the above steps, print the array arr[] as the resultant array.

Below is the implementation of the above approach:

C++

// C++ program for the above approach #include <iostream> using namespace std; // Function for merging the two sorted // arrays void merge(int a[], int l, int m, int r) {  int s1 = m - l + 1;  int s2 = r - m;  // Create two temp arrays  int left[s1];  int right[s2];  // Copy elements to left array  for (int i = 0; i < s1; i++)  left[i] = a[l + i];  // Copy elements to right array  for (int j = 0; j < s2; j++)  right[j] = a[j + m + 1];  int i = 0, j = 0, k = l;  // Merge the array back into the  // array over the range [l, r]  while (i < s1 && j < s2) {  // If the current left element  // is smaller than the current  // right element  if (left[i] <= right[j]) {  a[k] = left[i];  i++;  }  // Otherwise  else {  a[k] = right[j];  j++;  }  k++;  }  // Copy the remaining elements of  // the array left[]  while (i < s1) {  a[k] = left[i];  i++;  k++;  }  // Copy the remaining elements of  // the array right[]  while (j < s2) {  a[k] = right[j];  j++;  k++;  } } // Function to sort the array over the // range [l, r] void mergesort(int arr[], int l, int r) {  if (l < r) {  // Find the middle index  int mid = l + (r - l) / 2;  // Recursively call for the  // two halves  mergesort(arr, l, mid);  mergesort(arr, mid + 1, r);  // Perform the merge operation  merge(arr, l, mid, r);  } } // Function to sort an array for the // last m elements are unsorted void sortlastMElements(int arr[], int N,  int M) {  int s = M + N - 1;  // Sort the last m elements  mergesort(arr, N, s);  // Merge the two sorted subarrays  merge(arr, 0, N - 1, N + M - 1);  // Print the sorted array  for (int i = 0; i < N + M; i++)  cout << arr[i] << " "; } // Driver Code int main() {  int N = 3;  int M = 5;  int arr[] = { 2, 8, 10, 17, 15,  23, 4, 12 };  sortlastMElements(arr, N, M);  return 0; }

Java

// Java program for the above approach import java.util.*; class GFG{ // Function for merging the two sorted // arrays static void merge(int a[], int l, int m, int r) {  int s1 = m - l + 1;  int s2 = r - m;  // Create two temp arrays  int left[] = new int[s1];  int right[] = new int[s2];  // Copy elements to left array  for (int i = 0; i < s1; i++)  left[i] = a[l + i];  // Copy elements to right array  for (int j = 0; j < s2; j++)  right[j] = a[j + m + 1];  int i = 0, j = 0, k = l;  // Merge the array back into the  // array over the range [l, r]  while (i < s1 && j < s2) {  // If the current left element  // is smaller than the current  // right element  if (left[i] <= right[j]) {  a[k] = left[i];  i++;  }  // Otherwise  else {  a[k] = right[j];  j++;  }  k++;  }  // Copy the remaining elements of  // the array left[]  while (i < s1) {  a[k] = left[i];  i++;  k++;  }  // Copy the remaining elements of  // the array right[]  while (j < s2) {  a[k] = right[j];  j++;  k++;  } } // Function to sort the array over the // range [l, r] static void mergesort(int arr[], int l, int r) {  if (l < r) {  // Find the middle index  int mid = l + (r - l) / 2;  // Recursively call for the  // two halves  mergesort(arr, l, mid);  mergesort(arr, mid + 1, r);  // Perform the merge operation  merge(arr, l, mid, r);  } } // Function to sort an array for the // last m elements are unsorted static void sortlastMElements(int arr[], int N,  int M) {  int s = M + N - 1;  // Sort the last m elements  mergesort(arr, N, s);  // Merge the two sorted subarrays  merge(arr, 0, N - 1, N + M - 1);  // Print the sorted array  for (int i = 0; i < N + M; i++)  System.out.print( arr[i] + " "); } // Driver Code public static void main(String[] args) {  int N = 3;  int M = 5;  int arr[] = { 2, 8, 10, 17, 15,  23, 4, 12 };  sortlastMElements(arr, N, M); } } // This code is contributed by code_hunt.

Python3

# Python3 program for the above approach # Function for merging the two sorted # arrays def merge(a, l, m, r): s1 = m - l + 1 s2 = r - m # Create two temp arrays left = [0 for i in range(s1)] right = [0 for i in range(s2)] # Copy elements to left array for i in range(s1): left[i] = a[l + i] # Copy elements to right array for j in range(s2): right[j] = a[j + m + 1] i = 0 j = 0 k = l # Merge the array back into the # array over the range [l, r] while (i < s1 and j < s2): # If the current left element # is smaller than the current # right element if (left[i] <= right[j]): a[k] = left[i] i += 1 # Otherwise else: a[k] = right[j] j += 1 k += 1 # Copy the remaining elements of # the array left[] while (i < s1): a[k] = left[i] i += 1 k += 1 # Copy the remaining elements of # the array right[] while (j < s2): a[k] = right[j] j += 1 k += 1 # Function to sort the array over the # range [l, r] def mergesort(arr, l, r): if (l < r): # Find the middle index mid = l + (r - l) // 2 # Recursively call for the # two halves mergesort(arr, l, mid) mergesort(arr, mid + 1, r) # Perform the merge operation merge(arr, l, mid, r) # Function to sort an array for the # last m elements are unsorted def sortlastMElements(arr, N, M): s = M + N - 1 # Sort the last m elements mergesort(arr, N, s) # Merge the two sorted subarrays merge(arr, 0, N - 1, N + M - 1) # Print the sorted array for i in range(N + M): print(arr[i], end = " ") # Driver Code if __name__ == '__main__': N = 3 M = 5 arr = [ 2, 8, 10, 17, 15, 23, 4, 12 ] sortlastMElements(arr, N, M) # This code is contributed by ipg2016107

// C# program for the above approach using System; class GFG { // Function for merging the two sorted // arrays static void merge(int[] a, int l, int m, int r) {  int s1 = m - l + 1;  int s2 = r - m;  int i = 0, j = 0;    // Create two temp arrays  int[] left = new int[s1];  int[] right = new int[s2];    // Copy elements to left array  for (i = 0; i < s1; i++)  left[i] = a[l + i];    // Copy elements to right array  for (j = 0; j < s2; j++)  right[j] = a[j + m + 1];    int k = l;      // Merge the array back into the  // array over the range [l, r]  while (i < s1 && j < s2) {    // If the current left element  // is smaller than the current  // right element  if (left[i] <= right[j]) {  a[k] = left[i];  i++;  }    // Otherwise  else {  a[k] = right[j];  j++;  }  k++;  }    // Copy the remaining elements of  // the array left[]  while (i < s1) {  a[k] = left[i];  i++;  k++;  }    // Copy the remaining elements of  // the array right[]  while (j < s2) {  a[k] = right[j];  j++;  k++;  } }   // Function to sort the array over the // range [l, r] static void mergesort(int[] arr, int l, int r) {  if (l < r) {    // Find the middle index  int mid = l + (r - l) / 2;    // Recursively call for the  // two halves  mergesort(arr, l, mid);  mergesort(arr, mid + 1, r);    // Perform the merge operation  merge(arr, l, mid, r);  } }   // Function to sort an array for the // last m elements are unsorted static void sortlastMElements(int[] arr, int N,  int M) {  int s = M + N - 1;    // Sort the last m elements  mergesort(arr, N, s);    // Merge the two sorted subarrays  merge(arr, 0, N - 1, N + M - 1);    // Print the sorted array  for (int i = 0; i < N + M; i++)  Console.Write( arr[i] + " "); } // Driver code static void Main() {  int N = 3;  int M = 5;  int[] arr = { 2, 8, 10, 17, 15,  23, 4, 12 };  sortlastMElements(arr, N, M); } } // This code is contributed by sanjoy_62.

JavaScript

<script> // JavaScript program for the above approach // Function for merging the two sorted // arrays function merge(a, l, m, r) {  let s1 = m - l + 1;  let s2 = r - m;  // Create two temp arrays  let left = new Array(s1);  let right = new Array(s2);  // Copy elements to left array  for (let i = 0; i < s1; i++)  left[i] = a[l + i];  // Copy elements to right array  for (let j = 0; j < s2; j++)  right[j] = a[j + m + 1];  let i = 0, j = 0, k = l;  // Merge the array back into the  // array over the range [l, r]  while (i < s1 && j < s2) {  // If the current left element  // is smaller than the current  // right element  if (left[i] <= right[j]) {  a[k] = left[i];  i++;  }  // Otherwise  else {  a[k] = right[j];  j++;  }  k++;  }  // Copy the remaining elements of  // the array left[]  while (i < s1) {  a[k] = left[i];  i++;  k++;  }  // Copy the remaining elements of  // the array right[]  while (j < s2) {  a[k] = right[j];  j++;  k++;  } } // Function to sort the array over the // range [l, r] function mergesort(arr, l, r) {  if (l < r) {  // Find the middle index  let mid = Math.floor(l + (r - l) / 2);  // Recursively call for the  // two halves  mergesort(arr, l, mid);  mergesort(arr, mid + 1, r);  // Perform the merge operation  merge(arr, l, mid, r);  } } // Function to sort an array for the // last m elements are unsorted function sortlastMElements(arr, N, M) {  let s = M + N - 1;  // Sort the last m elements  mergesort(arr, N, s);  // Merge the two sorted subarrays  merge(arr, 0, N - 1, N + M - 1);  // Print the sorted array  for (let i = 0; i < N + M; i++)  document.write(arr[i] + " "); } // Driver Code let N = 3; let M = 5; let arr = [2, 8, 10, 17, 15,  23, 4, 12]; sortlastMElements(arr, N, M); </script>