#include <stdio.h>
/*
merge() — merges two sorted halves of an array into one sorted array.
Parameters:
arr[] — the main array
left — starting index of the left half
mid — ending index of the left half
right — ending index of the right half
*/
void merge(int arr[], int left, int mid, int right) {
int i = left; // index for left subarray
int j = mid + 1; // index for right subarray
int k = 0; // index for temporary array
int temp[right - left + 1]; // temporary array to store merged result
// Merge the two halves into temp[]
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// Copy remaining elements of left half (if any)
while (i <= mid) {
temp[k++] = arr[i++];
}
// Copy remaining elements of right half (if any)
while (j <= right) {
temp[k++] = arr[j++];
}
// Copy sorted temp[] back into arr[]
for (i = left, k = 0; i <= right; i++, k++) {
arr[i] = temp[k];
}
}
/*
mergeSort() — recursively divides the array into halves,
sorts each half, and merges them.
*/
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// Recursively sort left half
mergeSort(arr, left, mid);
// Recursively sort right half
mergeSort(arr, mid + 1, right);
// Merge the two sorted halves
merge(arr, left, mid, right);
}
}
/*
printArray() — prints the elements of an array
*/
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {88, 17, 36, 4, 9, 91, 15};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, size);
mergeSort(arr, 0, size - 1);
printf("Sorted array:\n");
printArray(arr, size);
return 0;
}
/*
run:
Original array:
88 17 36 4 9 91 15
Sorted array:
4 9 15 17 36 88 91
*/
