Mergesort in C++

Mergesort is a comparison-based sorting algorithm that uses the divide-and-conquer technique to efficiently sort an array or list of elements. It is one of the most popular sorting algorithms due to its simplicity, efficiency, and low space complexity. In this article, we will discuss the basics of mergesort, how it works, its time and space complexities, and some examples of its implementation in C++. 

What is Mergesort?

Mergesort is a comparison-based sorting algorithm that works by splitting the list of elements into two halves, sorting each half individually, and then merging them back together in sorted order. It is a recursive algorithm, meaning that it solves the problem by breaking it down into smaller subproblems until the base case is reached. The base case is when the list contains only one element, which is already sorted. 

Mergesort is a stable sorting algorithm, meaning that the relative order of elements with the same key value is preserved. It is also an in-place sorting algorithm, meaning that it only requires a constant amount of extra space, regardless of the size of the list. 

How Mergesort Works

Mergesort works by breaking the list of elements into two halves, sorting each half individually, and then merging them back together in sorted order.

The first step is to divide the list into two halves. This is done by finding the middle element of the list, and then splitting the list into two halves, one before the middle element and one after the middle element. 

The next step is to sort each half. This is done by recursively calling the mergesort algorithm on each half. 

Once the two halves have been sorted, they are merged back together in sorted order. This is done by comparing the first elements of each half and taking the smaller element. This element is then added to the sorted list and the process is repeated until all elements from both halves have been added to the sorted list. 

Time Complexity

Mergesort has a best-case time complexity of O(n log n), an average-case time complexity of O(n log n), and a worst-case time complexity of O(n log n). This means that the time complexity of mergesort is the same regardless of the input. 

Space Complexity

Mergesort has a worst-case space complexity of O(n). This means that it requires an additional space of size O(n) to sort a list of n elements. 

Implementation in C++

Now that we have discussed the basics of mergesort, let’s take a look at how to implement it in C++. 

The first step is to create a function for the mergesort algorithm. This function should take an array of elements and the size of the array as parameters. 

// Function to merge two halves 
void merge(int array[], int left, int mid, int right) 
{ 
	// Create two auxiliary arrays 
	// to store elements of the left 
	// and right halves of the array 
	int leftSize = mid - left + 1; 
	int rightSize = right - mid; 
	int leftArray[leftSize], rightArray[rightSize]; 
	
	// Copy elements of the left half 
	// into the left auxiliary array 
	for (int i = 0; i < leftSize; i++) 
		leftArray[i] = array[left + i]; 
	
	// Copy elements of the right half 
	// into the right auxiliary array 
	for (int j = 0; j < rightSize; j++) 
		rightArray[j] = array[mid + 1 + j]; 
	
	// Merge the two halves 
	int i = 0, j = 0; 
	int k = left; 
	while (i < leftSize && j < rightSize) 
	{ 
		if (leftArray[i] <= rightArray[j]) 
			array[k++] = leftArray[i++]; 
		else
			array[k++] = rightArray[j++]; 
	} 
	
	// Copy remaining elements 
	while (i < leftSize) 
		array[k++] = leftArray[i++]; 
	
	while (j < rightSize) 
		array[k++] = rightArray[j++]; 
} 

// Function to divide the array 
// into two halves, sort each 
// half and merge them 
void mergeSort(int array[], int left, int right) 
{ 
	if (left < right) 
	{ 
		// Find the middle element 
		int mid = left + (right - left) / 2; 
	
		// Sort the left half 
		mergeSort(array, left, mid); 
	
		// Sort the right half 
		mergeSort(array, mid + 1, right); 
	
		// Merge the sorted halves 
		merge(array, left, mid, right); 
	} 
} 

// Function to print the array 
void printArray(int array[], int size) 
{ 
	for (int i = 0; i < size; i++) 
		cout << array[i] << " "; 
	cout << endl; 
} 

// Driver code 
int main() 
{ 
	int array[] = {10, 5, 6, 3, 2, 1, 8}; 
	int size = sizeof(array) / sizeof(array[0]); 
	
	// Print the array before sorting 
	cout << "Array before sorting: "; 
	printArray(array, size); 
	
	// Sort the array 
	mergeSort(array, 0, size - 1); 
	
	// Print the array after sorting 
	cout << "Array after sorting: "; 
	printArray(array, size); 
	
	return 0; 
} 

Conclusion

In this article, we discussed the basics of mergesort, how it works, its time and space complexities, and how to implement it in C++. Mergesort is a comparison-based sorting algorithm that works by splitting the list of elements into two halves, sorting each half individually, and then merging them back together in sorted order. It is a recursive algorithm, meaning that it solves the problem by breaking it down into smaller subproblems until the base case is reached. Mergesort has a best-case time complexity of O(n log n), an average-case time complexity of O(n log n), and a worst-case time complexity of O(n log n). It also has a worst-case space complexity of O(n).

Exercises

// Function to merge two halves 
void merge(int array[], int left, int mid, int right) 
{ 
	// Create two auxiliary arrays 
	// to store elements of the left 
	// and right halves of the array 
	int leftSize = mid - left + 1; 
	int rightSize = right - mid; 
	int leftArray[leftSize], rightArray[rightSize]; 
	
	// Copy elements of the left half 
	// into the left auxiliary array 
	for (int i = 0; i < leftSize; i++) 
		leftArray[i] = array[left + i]; 
	
	// Copy elements of the right half 
	// into the right auxiliary array 
	for (int j = 0; j < rightSize; j++) 
		rightArray[j] = array[mid + 1 + j]; 
	
	// Merge the two halves 
	int i = 0, j = 0; 
	int k = left; 
	while (i < leftSize && j < rightSize) 
	{ 
		if (leftArray[i] <= rightArray[j]) 
			array[k++] = leftArray[i++]; 
		else
			array[k++] = rightArray[j++]; 
	} 
	
	// Copy remaining elements 
	while (i < leftSize) 
		array[k++] = leftArray[i++]; 
	
	while (j < rightSize) 
		array[k++] = rightArray[j++]; 
} 

// Function to divide the array 
// into two halves, sort each 
// half and merge them 
void mergeSort(int array[], int left, int right) 
{ 
	if (left < right) 
	{ 
		// Find the middle element 
		int mid = left + (right - left) / 2; 
	
		// Sort the left half 
		mergeSort(array, left, mid); 
	
		// Sort the right half 
		mergeSort(array, mid + 1, right); 
	
		// Merge the sorted halves 
		merge(array, left, mid, right); 
	} 
} 

// Function to print an array 
void printArray(int array[], int size) 
{ 
	for (int i = 0; i < size; i++) 
		cout << array[i] << " "; 
	cout << endl; 
} 

// Function to merge two sorted arrays 
void mergeArrays(int array1[], int array2[], int n1, int n2, int array3[]) 
{ 
	int i = 0, j = 0, k = 0; 

	// Traverse both arrays 
	while (i<n1 && j <n2) 
	{ 
		// Check if current element of first 
		// array is smaller than current element 
		// of second array. If yes, store first 
		// array element and increment first array 
		// index. Otherwise do same with second array 
		if (array1[i] < array2[j]) 
			array3[k++] = array1[i++]; 
		else
			array3[k++] = array2[j++]; 
	} 

	// Store remaining elements of first array 
	while (i < n1) 
		array3[k++] = array1[i++]; 

	// Store remaining elements of second array 
	while (j < n2) 
		array3[k++] = array2[j++]; 
} 

// Function to find the middle element 
// of a list 
int findMiddle(int array[], int size) 
{ 
	// Middle element is the middle index 
	// of the list 
	return array[size / 2]; 
} 

// Function to check if an array is sorted 
bool isSorted(int array[], int size) 
{ 
	// Traverse through the array 
	for (int i = 0; i < size - 1; i++) 
	{ 
		// Check if the current element is 
		// greater than the next element 
		if (array[i] > array[i + 1]) 
			return false; 
	} 
	
	// If all elements are in order, 
	// array is sorted 
	return true; 
}