merge and quick sort

/*
Name: Hrithik Singh
*/



#include <stdio.h>
#include <stdlib.h>
#define MAX 30

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
int 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; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // 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 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++;
    }
}

/* 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) {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}



void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

/* The main function that implements QuickSort
 arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);

        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}


/* UTILITY FUNCTIONS */
/* 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");
}
//fuction for merge sort without recursion
int mergeSortwithout(int arr[],int size){
	int i=2,j=0;
	while(i<size){
		j=0;
		while(j<size-1){
			int right=(j+i)-1;
			int left =j;
			if(right>size){
				right=size-1;
			}
			int middle=(left +  right )/2;
			merge(arr,left,middle, right);
			j=j+1;
		}
		i=i*2;
		if(i>=size){
			i=i/2;
			merge(arr,0,size-1,(i-1));
			i=size;
		}
	}
}
/* Driver program to test above functions */
int main(){
    int n;
    int choice;
    printf("Enter the no. of elements in the list\n");
    scanf("%d",&n);
    printf("Enter the elements\n");
    int arr[n];
    for(int i=0;i<n;i++){
      scanf("%d",&arr[i]);
    }
    printf("\n");
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    do{
       printf("\n\n");
       printf("1.Print Array\n");
       printf("2.Sort array using merge sort with recursion\n");
       printf("3.Sort array using merge sort without recursion\n");
       printf("4.Sort array using Quick sort\n");
       printf("5.Exit\n");
       printf("Enter your choice:\n");
       scanf("%d",&choice);
       printf("\n\n");
       switch (choice) {
         case 1:
                printf("Given array is \n");
                printArray(arr, arr_size);
                printf("\n");
        break;
        case 2:
               mergeSort(arr, 0, arr_size - 1);
               printf("Sorted array using Merge Sort is\n");
               printArray(arr,arr_size);
               printf("\n");
        break;
        case 3:
              quickSort(arr,0,arr_size-1);
              printf("\nSorted array using Quick Sort is\n");
              printArray(arr, arr_size);
              printf("\n\n");
       break;
       case 4:
             mergeSortwithout(arr,arr_size);
             printArray(arr,arr_size);
       break;
       case 5:
              exit(0);
                        }
    }while(choice!=5);
}