Program for Merge Sort
1. Recursive Approach
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArr[n1], rightArr[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
while (i < n1) {
arr[k++] = leftArr[i++];
while (j < n2) {
arr[k++] = rightArr[j++];
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {70, 50, 30, 10, 20, 40, 60};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, size);
mergeSort(arr, 0, size - 1);
printf("\nSorted array:\n");
printArray(arr, size);
return 0;
OUTPUT:
Original array:
70 50 30 10 20 40 60
Sorted array:
10 20 30 40 50 60 70
2. Iterative Merge Sort
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArr[n1], rightArr[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
while (i < n1) {
arr[k++] = leftArr[i++];
while (j < n2) {
arr[k++] = rightArr[j++];
void iterativeMergeSort(int arr[], int n) {
int curr_size, left_start;
for (curr_size = 1; curr_size < n; curr_size *= 2) {
for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
int mid = left_start + curr_size - 1;
int right_end = (left_start + 2 * curr_size - 1 < n - 1) ?
(left_start + 2 * curr_size - 1) : (n - 1);
merge(arr, left_start, mid, right_end);
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, n);
iterativeMergeSort(arr, n);
printf("\nSorted array:\n");
printArray(arr, n);
return 0;
OUTPUT:
Original array:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13
