Sorting: Sort an array having partially sorted and partially unsorted array

Problem Statement:

You are given a 2 numbers N and M and an array[] whose size is “N+M”.

Here, The first N elements are sorted in ascending order, and the last M elements are unsorted.

You need to sort the given array in ascending order.

Example:

Input : N = 3, M = 4 arr = [1, 2, 3, 6, 5, 4, 3]

Output: [1, 2, 3, 3, 4, 5, 6]

Solution Explanation:

Simple solution is to sort whole array. But here we know which part of the array is unsorted.

So the efficient approach is to use merge sort on the unsorted part of the array.

Then merge 2 sorted array to make a single sorted array.

Time Complexity: O(m*log m)
Space Complexity: O(n+m)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void merge(int a[], int l, int m, int r)
{
    int s1 = m - l + 1;
    int s2 = r - m;

    int left[s1];
    int right[s2];

    for (int i = 0; i < s1; i++)
        left[i] = a[l + i];

    for (int j = 0; j < s2; j++)
        right[j] = a[j + m + 1];

    int i = 0, j = 0, k = l;

    while (i < s1 && j < s2) 
    {

        if (left[i] <= right[j]) 
        {
            a[k] = left[i];
            i++;
        }

        else 
        {
            a[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < s1) 
    {
        a[k] = left[i];
        i++;
        k++;
    }

    while (j < s2) 
    {
        a[k] = right[j];
        j++;
        k++;
    }
}


void mergeSort(int arr[], int l, int r)
{
    if (l < r) 
    {

        int mid = l + (r - l) / 2;

        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);

        merge(arr, l, mid, r);
    }
}

int main()
{
    int n = 3;
    int m = 4;
    int arr[] = { 1, 2, 3, 6, 5, 4, 3};

    int len = m + n - 1;
    mergeSort(arr, n, len);//to sort last m elements

    merge(arr, 0, n - 1, n + m - 1); //merge 2 subarrays


    for (int i = 0; i < n + m; i++)
        cout << arr[i] << " ";

    return 0;
}

Output

1 2 3 3 4 5 6