Let's zoom in on one of these merge steps, say merging [27, 38] and [3, 43]:
Compare 27 and 3: 3 is smaller, so it goes first. [3]
Compare 27 and 43: 27 is smaller. [3, 27]
38 is next smallest. [3, 27, 38]
43 is last. [3, 27, 38, 43]
This process happens for each merge step until we get our final sorted array.
Final sorted array: [3, 9, 10, 27, 38, 43, 82]
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
// Function to merge two sorted subarrays of vector v
void merge(vector<int> &v, int start, int end) {
// If the subarray has 0 or 1 element, it's already sorted
if (start >= end)
return;
// Calculate the middle point
int mid = (start + end) / 2;
// Calculate lengths of two subarrays
int len1 = mid - start + 1; // Length of left subarray
int len2 = end - mid; // Length of right subarray
// Create temporary arrays
int *left = new int[len1]; // Temporary array for left subarray
int *right = new int[len2]; // Temporary array for right subarray
// Copy data to temporary arrays
// Copy left subarray
int k = start;
for (int i = 0; i < len1; i++) {
left[i] = v[k];
k++;
}
// Copy right subarray
k = mid + 1;
for (int i = 0; i < len2; i++) {
right[i] = v[k];
k++;
}
// Merge the temporary arrays back into v[start..end]
int leftIndex = 0; // Index for left subarray
int rightIndex = 0; // Index for right subarray
int mainArrayIndex = start; // Index for main array
// Compare elements from both subarrays and place the smaller one in the main array
while (leftIndex < len1 && rightIndex < len2) {
if (left[leftIndex] < right[rightIndex]) {
v[mainArrayIndex] = left[leftIndex];
leftIndex++;
} else {
v[mainArrayIndex] = right[rightIndex];
rightIndex++;
}
mainArrayIndex++;
}
// Copy remaining elements of left subarray, if any
while (leftIndex < len1) {
// v[mainArrayIndex] = left[leftIndex];
// leftIndex++;
// mainArrayIndex++;
// The ABOVE 3 Lines can be Written as
v[mainArrayIndex++] = left[leftIndex++];
}
// Copy remaining elements of right subarray, if any
while (rightIndex < len2) {
v[mainArrayIndex] = right[rightIndex];
rightIndex++;
mainArrayIndex++;
}
// Free the memory allocated for temporary arrays
delete[] left;
delete[] right;
}
// Recursive function to sort an array using merge sort
void mergeSort(vector<int> &v, int start, int end) {
// Base case: if the subarray has 0 or 1 element, it's already sorted
if (start >= end)
return;
// Find the middle point to divide the array into two halves
int mid = (start + end) / 2;
// Recursively sort the left half
mergeSort(v, start, mid);
// Recursively sort the right half
mergeSort(v, mid + 1, end);
// Merge the sorted halves
merge(v, start, end);
}
int main() {
// Create a vector with unsorted integers
vector<int> v = {823, 45, 34, 93, 423, 42, 232, 23, 22, 2};
int size = v.size();
// Call mergeSort to sort the entire vector
mergeSort(v, 0, size - 1);
// Print the sorted vector
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
return 0;
}
In the code, the merge function is doing these comparison and rearrangement steps. It's creating temporary arrays to hold the split pieces, then merging them back into the main array in sorted order.
The mergeSort function is handling the recursive splitting and calling merge to put things back together.
int leftIndex = 0;
int rightIndex = 0;
int mainArrayIndex = start;
while (leftIndex < len1 && rightIndex < len2)
{
if (left[leftIndex] < right[rightIndex])
{
v[mainArrayIndex] = left[leftIndex++];
}
else
{
v[mainArrayIndex] = right[rightIndex++];
}
mainArrayIndex++;
}
This is where the magic happens! We compare elements from both halves and put the smaller one back into the main array ! and Handling LeftOvers !
Let's dive into each of these steps in a more descriptive approach:
Calculating sizes: Imagine you're splitting a deck of cards into two piles. You need to know how many cards are in each pile. That's what we're doing here:
len1 = mid - start + 1: This counts how many cards are in the left pile.
len2 = end - mid: This counts how many cards are in the right pile. These calculations ensure we know exactly how big our temporary arrays need to be.
Creating temporary arrays: Now that we know how big our piles are, we're creating two new, smaller decks to hold these cards temporarily:
int *left = new int[len1]: This is like getting a new, empty box that can hold exactly len1 cards.
int *right = new int[len2]: Another new box, this time for len2 cards. These temporary arrays give us a workspace to sort our cards without messing up the original deck.
Copying data to temp arrays: This step is like dealing cards into our new boxes:
We start at the beginning of our section (k = start) and deal cards one by one into the left box.
Then we move to the middle (k = mid + 1) and deal the rest into the right box. This process copies our data so we can work with it without changing the original array.
Merging logic: This is the heart of the merge sort. Imagine you have two piles of sorted cards, and you're combining them into one sorted pile:
You look at the top card of each pile.
You take the smaller card and put it into your final pile.
You keep doing this until one pile is empty. This process ensures that as you build your new pile, it stays in order from smallest to largest.
Handling leftovers: After the main merging, one pile might still have cards left:
If the left pile has cards, we add them all to the end of our final pile.
If the right pile has cards, we do the same with those. This step ensures we don't forget any cards and that all of them end up in our final, sorted pile.
Cleaning up: Remember those temporary boxes we created? We don't need them anymore:
delete[] left: This is like recycling the left box.
delete[] right: And here we recycle the right box. In programming terms, we're freeing the memory we allocated earlier. This is important to prevent memory leaks, which can slow down or crash our program if we forget to clean up.
#include <vector>
#include <iostream>
using namespace std;
// Function to merge two sorted subarrays of vector v
void merge(vector<int> &v, int start, int end) {
// If the subarray has 0 or 1 element, it's already sorted
if (start >= end)
return;
vector<int> temp; // Temporary array to store the merged subarray
// Calculate the middle point
int mid = (start + end) / 2;
// Pointers to traverse the two subarrays
int leftPart = start; // Starting index of the left subarray
int rightPart = mid + 1; // Starting index of the right subarray
// Merge the two subarrays into the temp array
while (leftPart <= mid && rightPart <= end) {
// Compare elements from both subarrays and pick the smaller one
if (v[leftPart] <= v[rightPart]) {
temp.push_back(v[leftPart++]); // Add from the left subarray
} else {
temp.push_back(v[rightPart++]); // Add from the right subarray
}
}
// Copy any remaining elements from the left subarray
while (leftPart <= mid) {
temp.push_back(v[leftPart++]);
}
// Copy any remaining elements from the right subarray
while (rightPart <= end) {
temp.push_back(v[rightPart++]);
}
// Copy the merged elements back to the original vector
for (int index = start, x = 0; index <= end; index++) {
v[index] = temp[x++]; // Assign sorted values back to the original array
}
}
// Recursive function to sort an array using merge sort
void mergeSort(vector<int> &v, int start, int end) {
// Base case: if the subarray has 0 or 1 element, it's already sorted
if (start >= end)
return;
// Find the middle point to divide the array into two halves
int mid = (start + end) / 2; // start + (end - start) / 2 // avoid overflow
// Recursively sort the left half
mergeSort(v, start, mid);
// Recursively sort the right half
mergeSort(v, mid + 1, end);
// Merge the sorted halves
merge(v, start, end);
}
int main() {
// Create a vector with unsorted integers
vector<int> v = {6, 3, 7, 2, 5, 4};
int size = v.size();
// Call mergeSort to sort the entire vector
mergeSort(v, 0, size - 1);
// Print the sorted vector
for (int i = 0; i < size; i++) {
cout << v[i] << " ";
}
return 0;
}
