mergesort.cpp

/* TODO: Try to write merge sort!  Prototypes are given below using vectors,
 * but if you would prefer, arrays are fine too. */

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <vector>
using std::vector;

/* This should take two SORTED vectors, L and R, and return another vector
 * which is sorted and contains all values from L and R. */
vector<int> merge(const vector<int>& L, const vector<int>& R){
vector<int> result;
size_t i = 0, j = 0;
// Merge two vectors and compare their elements
   while (i < L.size() && j < R.size()) {
	if (L[i] < R[j]) {
		result.push_back(L[i]);
		i++;
	} else {
		result.push_back(R[j]);
		j++;
	}
}
// Add remaining elements from L, if any
   while (i < L.size()) {
	result.push_back(L[i]);
	i++;
}
// Add remaining elements from R, if any
   while (j < R.size()) {
	result.push_back(R[j]);
	j++;
}

return result;
}

void mergeSort(vector<int>& V){
	if (V.size() <= 1) {
		return; // Base case: a vector of size 0 or 1 is already sorted
	}

	// Divide the vector into two halves
	size_t mid = V.size() / 2;
	vector<int> left(V.begin(), V.begin() + mid);  // Left half of the vector
	vector<int> right(V.begin() + mid, V.end());   // Right half of the vector

	// Recursively sort the two halves
	mergeSort(left);
	mergeSort(right);

	// Merge the sorted halves back into the original vector V
	V = merge(left, right);
}
int main()
{
		vector<int> nums;
		int x;

		// Input numbers from the user
		cout << "Enter numbers to be sorted (end with non-numeric input):\n";
		while (cin >> x) {
			nums.push_back(x);
		}

		// Call mergeSort to sort the numbers
		mergeSort(nums);

		// Output the sorted vector
		cout << "Sorted numbers: ";
		for (int num : nums) {
			cout << num << " ";
		}
		cout << endl;
		return 0;
}

// vim:foldlevel=2

/*Merge Sort is a divide-and-conquer algorithm:
*Divide the array into two halves.
*Recursively sort both halves.
*Merge the two sorted halves into a single sorted array.*/