Merge Sort

                                            Resource Link

GeeksForGeeks

Visualization

Hackerearth

হাসানের রাফখাতা

                                       Implementation:

	#include<bits/stdc++.h>
	using namespace std;
	int n;
	void print(int ar[])
	{
	for(int i = 0; i < n; i++){
	cout << ar[i] << " ";
	}
	cout << endl;
	}
	void merge(int A[], int start, int mid, int end)
	{
	int ar[end-start+1], k = 0; // store the starting position of both parts in temporary variables.
	int p = start, q = mid+1;
	for(int i = start; i <= end; i++){
	if(p > mid) // checks if first part comes to an end or not.
	ar[k++] = A[q++];
	else if(q > end) // checks if second part comes to an end or not.
	ar[k++] = A[p++];
	else if(A[p] < A[q])// checks which part has smaller element.
	ar[k++] = A[p++];
	else
	ar[k++] = A[q++];
	}
	for(int i = 0; i < k; i++){
	A[start++] = ar[i];
	}
	}
	void merge_sort(int A[], int start, int end)
	{
	if(start < end){
	int mid = (start+end)/2;
	merge_sort(A,start, mid);
	merge_sort(A, mid+1, end);
	merge(A,start, mid, end);
	}
	}
	int main()
	{
	cin >> n;
	int ar[n+5];
	for(int i = 0; i < n; i++){
	cin >> ar[i];
	}
	merge_sort(ar,0,n);
	print(ar);
	return 0;
	}

view raw merge_sort.cpp hosted with ❤ by GitHub

Share: