« Merge Sort a array

Problem

Sort an array A using Merge Sort. Change in the input array itself.

Input format :

Line 1 : Integer n i.e. Array size

Line 2 : Array elements (separated by space)

Output format :

Array elements in increasing order (separated by space)

Constraints :

1 <= n <= 10^3

Sample Input 1 :

6

2 6 8 5 4 3

Sample Output 1 :

2 3 4 5 6 8

Sample Input 2 :

5

2 1 5 2 3

Sample Output 2 :

1 2 2 3 5

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14void merge(int arr[], int start, int mid, int end)
15{
16    int n1 = mid - start + 1;
17    int n2 = end - mid;
18
19    int L[n1], R[n2];
20
21    for (int i = 0; i < n1; i++)
22    {
23        L[i] = arr[start + i];
24    }
25    for (int j = 0; j < n2; j++)
26    {
27        R[j] = arr[mid + 1 + j];
28    }
29
30    int i = 0;
31    int j = 0;
32    int k = start;
33
34    while (i < n1 && j < n2)
35    {
36        if (L[i] <= R[j])
37        {
38            arr[k] = L[i];
39            i++;
40        }
41        else
42        {
43            arr[k] = R[j];
44            j++;
45        }
46        k++;
47    }
48
49    while (i < n1)
50    {
51        arr[k] = L[i];
52        i++;
53        k++;
54    }
55
56    while (j < n2)
57    {
58        arr[k] = R[j];
59        j++;
60        k++;
61    }
62}
63
64void mergeSort(int *arr, int start, int end)
65{
66    if (start >= end)
67    {
68        return;
69    }
70    int mid = (start + end) / 2;
71    mergeSort(arr, start, mid);
72    mergeSort(arr, mid + 1, end);
73    merge(arr, start, mid, end);
74}
75int main()
76{
77    int length;
78    cin >> length;
79    int *arr = new int[length];
80    for (int i = 0; i < length; i++)
81    {
82        cin >> arr[i];
83    }
84    mergeSort(arr, 0, length - 1);
85    for (int i = 0; i < length; i++)
86    {
87        cout << arr[i] << endl;
88    }
89    return 0;
90}