মার্জ সর্ট ইমপ্লিমেন্টেশন ইন সি প্লাস প্লাস

	/**
	* Algorithm : Merge Sort
	* Writer : Mehadi Hasan Menon.
	**/
	#include <iostream>
	#include <vector>
	using namespace std;
	void merge(vector <int>& array, vector <int>& array1, vector <int>& array2)
	{
	array.clear();
	int i, j;
	for(i = 0, j = 0; i < array1.size() && j < array2.size(); )
	{
	if(array1.at(i) < array2.at(j)) {
	array.push_back(array1.at(i));
	i++;
	}
	else if(array1.at(i) > array2.at(j)) {
	array.push_back(array2.at(j));
	j++;
	}
	}
	// if something left in array1
	while(i < array1.size()) {
	array.push_back(array1.at(i));
	i++;
	}
	// if something left in array1
	while(j < array2.size()) {
	array.push_back(array2.at(j));
	j++;
	}
	}
	void merge_sort(vector <int>& array)
	{
	if(array.size() > 1)
	{
	// split 1st half
	vector <int> array1(array.begin(), array.begin() + array.size() / 2);
	merge_sort(array1);
	// split 2nd half
	vector <int> array2(array.begin() + array.size() / 2, array.end());
	merge_sort(array2);
	// merge sorted list
	merge(array, array1, array2);
	}
	}
	int main()
	{
	vector <int> array;
	array.push_back(3); array.push_back(10); array.push_back(17); array.push_back(2);
	merge_sort(array);
	for(int i = 0; i < array.size(); i++) {
	cout << array[i] << " ";
	}
	cout << endl;
	return 0;
	}

view raw marge_sort.cpp hosted with ❤ by GitHub