# include <stdio.h>
# include <stdlib.h>

int main(int argc,char *argv[])
{
int *array,i;
if(argc<3)
	{
	printf("\nInsufficient arguments provided\n");
	return(1);
	}

if((array=(int*)calloc(argc-1,sizeof(int)))==NULL)
	{
	printf("Error allocating memory");
	exit(1);
	}

for(i=1;i<argc;i++)
	{
	
	if(isalpha(*argv[i]))
	{
	printf("\nInvalid argument encountered\n");
	free(array);
	exit(1);
	}
	else
	array[i-1]=atoi(argv[i]);
		
	}
	       	
msort(array,0,argc-2);

for(i=0;i<argc-1;i++)
printf("\n%d",array[i]);

free(array);
return 0;
}


msort(int *array,int lower,int upper)
{
int temp,*arr,i,down,up,tempup;
if(upper-lower==1)
	{
	
	if(array[lower]>array[upper])
		{
		temp=array[upper];
		array[upper]=array[lower];
		array[lower]=temp;
		}
	
	}
else if(upper-lower>1)
	{
	msort(array,lower,(lower+upper)/2);
	msort(array,((lower+upper)/2)+1,upper);
	}

		if((arr=(int*)calloc(upper-lower+1,sizeof(int)))==NULL)
		{
		printf("Error allocating memory");
		return(1);
		}
	
	if((upper-lower+1)>2)
	{
	for(i=0;i<(upper-lower)+1;i++)
	arr[i]=array[lower+i];
	
	down=0;
	
	if((upper-lower+1)%2!=0)
		up=((upper-lower+1)/2)+1;
	else
		up=((upper-lower+1)/2);
	
	tempup=up;
	
		for(i=0;i<upper-lower+1;i++)
	{
	
		if(down==tempup)
		{
		array[lower+i]=arr[up];
		up++;	
		continue;
		}
		
	
		if(up>=(upper-lower+1))
		{
		array[lower+i]=arr[down];
		down++;
		continue;
		}
	
		if(arr[up]>arr[down])
		{
		array[lower+i]=arr[down];
		down++;	
		continue;
		}
		
	
		if(arr[up]<arr[down])
		{
		array[lower+i]=arr[up];
		up++;
		continue;
		}
	
		if(arr[up]==arr[down])
		{
		array[lower+i]=arr[up];
		up++;
		continue;
		}
		
		
	}
	
		free(arr);
	}

}

# include <stdio.h>
# include <stdlib.h>
# include <ctype.h>

void msort (int *, int, int);	/*Function prototypes for Merge sort and Insertion sort functions */
void insertion (int *a, int n);

int
main (int argc, char *argv[])
{
  int *array, i;		/*array to hold the digits passed from the command line */
  char ch = ' ';
  if (argc < 3)			/* If one or less than one argument is provided, there is no need of sorting */
    {
      printf ("\nInsufficient arguments provided\n");
      return (1);
    }

  if ((array =  calloc (argc - 1, sizeof (int))) == NULL)	/*Memmory is dynamically allocated to hold the arguments passed through command line */
    {
      printf ("Error allocating memory");	/*Any error is allocation of memory will result in an error message and the program exits */
      exit (1);
    }

  for (i = 1; i < argc; i++)	/*The given input is checked for validity by checking wheather its a number */
    {				/*If a valid number is found it is copied into the array */

      if (isalpha (**(argv + i)))
	{
	  printf ("\nInvalid argument encountered\n");
	  free (array);
	  exit (1);
	}
      else
	{
	  *(array + i - 1) = atoi (*(argv + i));
	}
    }

  /*The user is given the choice of using insertion or merge sort to sort the array */

  printf ("\n Press 'i' for insertion sort or 'm' for merge sort > ");
  while (ch != 'i' && ch != 'm')	/*Input is expected untill a valid input is gievn */
    ch = getchar ();

  /*Respective sorting functions are called based on the user input */

  (ch == 'm') ? (msort (array, 0, argc - 2)) : (insertion (array, argc - 1));

  /*The sorted array is displayed on the screen */

  for (i = 0; i < argc - 1; i++)
    printf ("\n%d", *(array + i));

  /*The allocated memory for the array is deallocated/freed */

  free (array);
  printf ("\n");		/*Displays prompt in the next line */
  return 0;
}



void
insertion (int a[], int n)	/*The insertion sort function accepts the array pointer and the number of elements as argument */
{
  int i, temphold, num;		/*Variables : i as counter, temphold used to swap, num to get value of i into while loop */
  for (i = 1; i < n; i++)	/*Loop will run till the last element is sorted */
    {
      num = i;
      /*
         The while loop is run until the elements in the left section below element i are ordered     
       */
      while (*(a + num) < *(a + num - 1))
	{
	  temphold = *(a + num);
	  *(a + num) = *(a + num - 1);
	  *(a + num - 1) = temphold;	/* The numbers are swapped */
	  if (num - 1 == 0)	/*The loop is broken when num reaches start of left section */
	    break;
	  else
	    num--;		/* Num is moved left to compare with the previous element */
	}
    }


  return;
}


void
msort (int array[], int lower, int upper)	/* The merge sort recursive function accepts the array pointer, lower and upper bound as arguments */
{

  int temp, *arr, i, down = 0, up, tempup;
/*
The below if block runs when the array is split into very small part 
and where only 2 elemets exist. So these 2 elemts are compared and sorted is proper order
*/
  if (upper - lower == 1)
    {

      if (*(array + lower) > *(array + upper))
	{
	  temp = *(array + upper);
	  *(array + upper) = *(array + lower);
	  *(array + lower) = temp;
	}

    }

/*
The below block is run if the array has more than 2 elements
Then the array is again split into 2 parts by calling the same function with different lower and upper bound
*/

  else if (upper - lower > 1)
    {
      msort (array, lower, (lower + upper) / 2);
      msort (array, ((lower + upper) / 2) + 1, upper);
    }


/*
The split arrays have to be merged (at least logically). This part happens in the below bloack
A temp array is created to hold the elements so that the 2 arrays can be merged (sorted)
*/
  if ((arr =  calloc (upper - lower + 1, sizeof (int))) == NULL)
    {
      printf ("Error allocating memory");
      return;
    }

  if ((upper - lower + 1) > 2)
    {
      for (i = 0; i < (upper - lower) + 1; i++)	/*The elements are copied into the temp array arr */
	*(arr + i) = *(array + lower + i);
/*
The upper bound is calculated differently when there are odd or even number of elements
in the array
*/
      ((upper - lower + 1) % 2) != 0 ? (up =
					((upper - lower + 1) / 2) + 1) : (up =
									  ((upper - lower + 1) / 2));
      tempup = up;		/*The upper bound is copied into another variable as this value is required later for some calculation */
      for (i = 0; i < upper - lower + 1; i++)	/*Upper-lower+1 gives the number of elements in the given section of the array */
	{

	  if (down == tempup)	/*When the lower bound of the temp array reaches the upper bound it means that the left part
				   or the section of the array is empty and there is no need to compare */
	    {
	      *(array + lower + i) = *(arr + up);
	      up++;
	    }

	  else if (up >= (upper - lower + 1))	/*When the upper bound of the temp array reaches the end of the array section it means that the right part
						   or the section of the array is empty and there is no need to compare */
	    {
	      *(array + lower + i) = *(arr + down);
	      down++;
	    }

	  else
	    /*
	       When the left and right part of the array contains elements the first elements in both the array are compared and
	       the smallest of the two is owerwritten to the main array location starting from lower bound. 

	       The first elements of the left section of temp array only need to be compared with 
	       with its right counterpart as both of them are already individually sorted
	     */
	    (*(arr + up) > *(arr + down)) ? (*(array + lower + i) =
					     *(arr + down),
					     down++) : (*(array + lower + i) =
							*(arr + up), up++);
	}
      free (arr);		/*The memory allocations are freed */
    }

  return;
}