#include <stdio.h>
// Function to merge two subarrays into a single sorted array
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1; // Size of the first subarray
int n2 = right - mid; // Size of the second subarray
// Temporary arrays to hold the two subarrays
int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into arr[left..right]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = left; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Function to implement Merge Sort using recursion
void mergeSort(int arr[], int left, int right)
{
if (left < right)
{
// Find the middle point to divide the array into two halves
int mid = left + (right - left) / 2;
// Call mergeSort on the first half
mergeSort(arr, left, mid);
// Call mergeSort on the second half
mergeSort(arr, mid + 1, right);
// Merge the two halves sorted in the previous steps
merge(arr, left, mid, right);
}
}
// Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is: \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is: \n");
printArray(arr, arr_size);
return 0;
}
Explanation:–
- Merge Sort Overview: Merge Sort is a divide-and-conquer algorithm that works by recursively dividing the array into smaller subarrays and then merging them back in sorted order. The key steps are:
- Divide the array into two halves.
- Recursively apply merge sort to both halves.
- Merge the two sorted halves back into a single sorted array.
2. mergeSort() Function:
- Base Case: If the array has one or no elements (i.e.,
left >= right), then the array is already sorted. - Recursive Case: The array is split into two halves, and
mergeSort()is called recursively on each half. - After sorting both halves, the
merge()function is used to merge the sorted halves back together.
3. merge() Function:
- This function merges two sorted subarrays into a single sorted array.
- The two subarrays are
[left..mid]and[mid+1..right]. - The merging process uses temporary arrays
L[]andR[]to hold the left and right subarrays. The elements fromL[]andR[]are compared, and the smaller element is added back to the original arrayarr[].
4. printArray() Function:
- This function simply prints the elements of the array.
5. Main Function:
- An array of integers is initialized, and its size is determined.
- The original (unsorted) array is printed.
- The
mergeSort()function is called to sort the array. - Finally, the sorted array is printed.
Output:-
When you run this program, you will see the following output:
Given array is:
12 11 13 5 6 7
Sorted array is:
5 6 7 11 12 13
How the Program Works:
- Initially, the array
[12, 11, 13, 5, 6, 7]is divided into two halves:[12, 11, 13][5, 6, 7]
- Each half is further divided:
[12, 11, 13]becomes[12, 11]and[13], and[12, 11]becomes[12]and[11].[5, 6, 7]becomes[5, 6]and[7], and[5, 6]becomes[5]and[6].
- Once the subarrays contain only one element, they are merged in sorted order:
[12]and[11]are merged into[11, 12].[5]and[6]are merged into[5, 6].
- This process continues until the entire array is merged back together in sorted order.
