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
Write a function to sort an array of integers using the mergesort algorithm.
// 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);
}
}
Write a function to print an array of integers in sorted order.
// Function to print an array
void printArray(int array[], int size)
{
for (int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
Write a function to merge two sorted arrays.
// 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++];
}
Write a function to find the middle element of a list.
// 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];
}
Write a function to check if an array is sorted.
// 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;
}