/* 
* Code example for CP264 Data Structures II
* Merge sort, recursive and iterative merge sort algorithms 
  source: https://www.geeksforgeeks.org/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); 
void merge_sort_recursive(int arr[], int l, int r);
void merge_sort_iterative(int arr[], int n);
int min(int x, int y);  
void print_array(int A[], int size); 

/* Driver program to test above functions */
int main() 
{ 
  int arr[] = {12, 11, 13, 5, 6, 7}; 
  int n = sizeof(arr)/sizeof(arr[0]);
  int i;
  int b[n];
    
  for (i=0; i<n; i++)
	b[i] = arr[i];

  printf("Given array: "); 
  print_array(b, n); 
  merge_sort_recursive(b, 0, n-1); 
  printf("\nSorted array: "); 
  print_array(b, n); 
  
  for (i=0; i<n; i++)
	b[i] = arr[i];
  
  merge_sort_iterative(b, n); 
  printf("\nSorted array: "); 
  print_array(b, n); 

  return 0; 
} 

/* Recursive merge sort function to sort arr[0...n-1] */
void merge_sort_recursive(int arr[], int l, int r) 
{ 
  if (l < r) 
  { 
	int m = l+(r-l)/2; 
	merge_sort_recursive(arr, l, m); 
	merge_sort_recursive(arr, m+1, r); 
	merge(arr, l, m, r); 
  } 
}   

/* Iterative merge sort function to sort arr[0...n-1] */
void merge_sort_iterative(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 = min(left_start + curr_size - 1, n-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++; 
    } 
} 
  
int min(int x, int y) 
{ 
  return (x<y)? x :y; 
} 

void print_array(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
      printf("%d ", A[i]); 
    printf("\n"); 
}