Sorting-Algorithms/MergeSort.cpp at master · bishworup11/Sorting-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
void merge(int arr[], int low, int hi, int mid)
{

  int i = low;
  int j = mid + 1;
  int k = low;
  int b[hi];

  while (i <= mid && j <= hi)
  {
    if (arr[i] <= arr[j])
    {
      b[k] = arr[i];
      k++;
      i++;

    }

    else if (arr[j] < arr[i])
    {
      b[k] = arr[j];
      j++;
      k++;
    }

  }

  if (i > mid)
  {

    while (j <= hi)
    {

      b[k] = arr[j];
      k++;
      j++;

    }
  }

  else if (j > hi)
  {

    while (i <= mid)
    {

      b[k] = arr[i];
      k++;
      i++;


    }
  }


  for (int i = low; i <= hi; ++i)
  {
    arr[i] = b[i];
  }

}


void MergeSort(int arr[], int low , int hi )
{
  int mid;

  if (low < hi)
  {
    mid = (low + hi) / 2;

    MergeSort(arr, low, mid);
    MergeSort(arr, mid + 1, hi);

    merge(arr, low, hi, mid);

  }


}

void display(int arr[], int n)
{

  for (int i = 0; i < n; i++)
  {

    cout << arr[i] << " ";
  }
}

int main()
{
  int n;

  printf("input the array length\n");

  cin >> n;
  int ar[n];
  for (int i = 0; i < n; i++)
  {

    cin >> ar[i];
  }
  MergeSort(ar, 0, n - 1);

  display(ar, n);


}