Iterative Merge Sort

Following is a typical recursive implementation of Merge Sort that uses last element as pivot.

/* Recursive C program for merge sort */ #include<stdlib.h> #include<stdio.h>   /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */ void merge(int arr[], int l, int m, int r);   /* l is for left index and r is right index of the sub-array   of arr to be sorted */ void mergeSort(int arr[], int l, int r) {    if (l < r)    {       int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h       mergeSort(arr, l, m);       mergeSort(arr, m+1, r);       merge(arr, l, m, r);    } }   /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */ void merge(int arr[], int l, int m, int r) {     int i, j, k;     int n1 = m - l + 1;     int n2 =  r - m;       /* create temp arrays */     int L[n1], R[n2];       /* Copy data to temp arrays L[] and R[] */     for (i = 0; i < n1; i++)         L[i] = arr[l + i];     for (j = 0; j < n2; j++)         R[j] = arr[m + 1+ j];       /* Merge the temp arrays back into arr[l..r]*/     i = 0;     j = 0;     k = l;     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 there are any */     while (i < n1)     {         arr[k] = L[i];         i++;         k++;     }       /* Copy the remaining elements of R[], if there are any */     while (j < n2)     {         arr[k] = R[j];         j++;         k++;     } }   /* Function to print an array */ void printArray(int A[], int size) {     int i;     for (i=0; i < size; i++)         printf("%d ", A[i]);     printf("\n"); }   /* Driver program to test above functions */ 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; }

Output:

Given array is
12 11 13 5 6 7

Sorted array is
5 6 7 11 12 13

Iterative Merge Sort:
The above function is recursive, so uses function call stack to store intermediate values of l and h. The function call stack stores other bookkeeping information together with parameters. Also, function calls involve overheads like storing activation record of the caller function and then resuming execution. Unlike Iterative QuickSort, the iterative MergeSort doesn’t require explicit auxiliary stack.
The above function can be easily converted to iterative version. Following is iterative Merge Sort.

/* Iterative C program for merge sort */ #include<stdlib.h> #include<stdio.h>   /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */ void merge(int arr[], int l, int m, int r);   // Utility function to find minimum of two integers int min(int x, int y) { return (x<y)? x :y; }     /* Iterative mergesort function to sort arr[0...n-1] */ void mergeSort(int arr[], int n) {    int curr_size;  // For current size of subarrays to be merged                    // curr_size varies from 1 to n/2    int left_start; // For picking starting index of left subarray                    // to be merged      // Merge subarrays in bottom up manner.  First merge subarrays of    // size 1 to create sorted subarrays of size 2, then merge subarrays    // of size 2 to create sorted subarrays of size 4, and so on.    for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)    {        // Pick starting point of different subarrays of current size        for (left_start=0; left_start<n-1; left_start += 2*curr_size)        {            // Find ending point of left subarray. mid+1 is starting            // point of right            int mid = left_start + curr_size - 1;              int right_end = min(left_start + 2*curr_size - 1, n-1);              // Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]            merge(arr, left_start, mid, right_end);        }    } }   /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */ void merge(int arr[], int l, int m, int r) {     int i, j, k;     int n1 = m - l + 1;     int n2 =  r - m;       /* create temp arrays */     int L[n1], R[n2];       /* Copy data to temp arrays L[] and R[] */     for (i = 0; i < n1; i++)         L[i] = arr[l + i];     for (j = 0; j < n2; j++)         R[j] = arr[m + 1+ j];       /* Merge the temp arrays back into arr[l..r]*/     i = 0;     j = 0;     k = l;     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 there are any */     while (i < n1)     {         arr[k] = L[i];         i++;         k++;     }       /* Copy the remaining elements of R[], if there are any */     while (j < n2)     {         arr[k] = R[j];         j++;         k++;     } }   /* Function to print an array */ void printArray(int A[], int size) {     int i;     for (i=0; i < size; i++)         printf("%d ", A[i]);     printf("\n"); }   /* Driver program to test above functions */ int main() {     int arr[] = {12, 11, 13, 5, 6, 7};     int n = sizeof(arr)/sizeof(arr[0]);       printf("Given array is \n");     printArray(arr, n);       mergeSort(arr, n);       printf("\nSorted array is \n");     printArray(arr, n);     return 0; }

Output:

Given array is
12 11 13 5 6 7

Sorted array is
5 6 7 11 12 13

Time complexity of above iterative function is same as recursive, i.e., Θ(nLogn).