#include         #include         #include         #include         #define MAX_ELEMENT_IN_ARRAY 1000000001   int     cmpfunc  (  const     void     *  a       const     void     *  b  )   {      // Compare function used by qsort      return     (  *  (  int     *  )  a     -     *  (  int     *  )  b  );   }   int     *  generate_random_array  (  int     n  )   {      srand  (  time  (  NULL  ));      int     *  a     =     malloc  (  sizeof  (  int  )     *     n  );      int     i  ;      for     (  i     =     0  ;     i      <     n  ;     ++  i  )      a  [  i  ]     =     rand  ()     %     MAX_ELEMENT_IN_ARRAY  ;      return     a  ;   }   int     *  copy_array  (  int     a  []     int     n  )   {      int     *  arr     =     malloc  (  sizeof  (  int  )     *     n  );      int     i  ;      for     (  i     =     0  ;     i      <     n  ;     ++  i  )      arr  [  i  ]     =     a  [  i  ];      return     arr  ;   }   // Code for Insertion Sort   void     insertion_sort_asc  (  int     a  []     int     start       int     end  )   {      int     i  ;      for     (  i     =     start     +     1  ;     i      <=     end  ;     ++  i  )      {      int     key     =     a  [  i  ];      int     j     =     i     -     1  ;      while     (  j     >=     start     &&     a  [  j  ]     >     key  )      {      a  [  j     +     1  ]     =     a  [  j  ];      --  j  ;      }      a  [  j     +     1  ]     =     key  ;      }   }   // Code for Merge Sort   void     merge  (  int     a  []     int     start       int     end       int     mid  )   {      int     i     =     start       j     =     mid     +     1       k     =     0  ;      int     *  aux     =     malloc  (  sizeof  (  int  )     *     (  end     -     start     +     1  ));      while     (  i      <=     mid     &&     j      <=     end  )      {      if     (  a  [  i  ]      <=     a  [  j  ])      aux  [  k  ++  ]     =     a  [  i  ++  ];      else      aux  [  k  ++  ]     =     a  [  j  ++  ];      }      while     (  i      <=     mid  )      aux  [  k  ++  ]     =     a  [  i  ++  ];      while     (  j      <=     end  )      aux  [  k  ++  ]     =     a  [  j  ++  ];      j     =     0  ;      for     (  i     =     start  ;     i      <=     end  ;     ++  i  )      a  [  i  ]     =     aux  [  j  ++  ];      free  (  aux  );   }   void     _merge_sort  (  int     a  []     int     start       int     end  )   {      if     (  start      <     end  )      {      int     mid     =     start     +     (  end     -     start  )     /     2  ;      _merge_sort  (  a       start       mid  );      _merge_sort  (  a       mid     +     1       end  );      merge  (  a       start       end       mid  );      }   }   void     merge_sort  (  int     a  []     int     n  )   {      return     _merge_sort  (  a       0       n     -     1  );   }   void     insertion_and_merge_sort_combine  (  int     a  []     int     start       int     end       int     k  )   {      // Performs insertion sort if size of array is less than or equal to k      // Otherwise uses mergesort      if     (  start      <     end  )      {      int     size     =     end     -     start     +     1  ;      if     (  size      <=     k  )      {      return     insertion_sort_asc  (  a       start       end  );      }      int     mid     =     start     +     (  end     -     start  )     /     2  ;      insertion_and_merge_sort_combine  (  a       start       mid       k  );      insertion_and_merge_sort_combine  (  a       mid     +     1       end       k  );      merge  (  a       start       end       mid  );      }   }   void     test_sorting_runtimes  (  int     size       int     num_of_times  )   {      // Measuring the runtime of the sorting algorithms      int     number_of_times     =     num_of_times  ;      int     t     =     number_of_times  ;      int     n     =     size  ;      double     insertion_sort_time     =     0       merge_sort_time     =     0  ;      double     merge_sort_and_insertion_sort_mix_time     =     0       qsort_time     =     0  ;      while     (  t  --  )      {      clock_t     start       end  ;      int     *  a     =     generate_random_array  (  n  );      int     *  b     =     copy_array  (  a       n  );      start     =     clock  ();      insertion_sort_asc  (  b       0       n     -     1  );      end     =     clock  ();      insertion_sort_time     +=     ((  double  )(  end     -     start  ))     /     CLOCKS_PER_SEC  ;      free  (  b  );      int     *  c     =     copy_array  (  a       n  );      start     =     clock  ();      merge_sort  (  c       n  );      end     =     clock  ();      merge_sort_time     +=     ((  double  )(  end     -     start  ))     /     CLOCKS_PER_SEC  ;      free  (  c  );      int     *  d     =     copy_array  (  a       n  );      start     =     clock  ();      insertion_and_merge_sort_combine  (  d       0       n     -     1       40  );      end     =     clock  ();      merge_sort_and_insertion_sort_mix_time     +=     ((  double  )(  end     -     start  ))     /     CLOCKS_PER_SEC  ;      free  (  d  );      start     =     clock  ();      qsort  (  a       n       sizeof  (  int  )     cmpfunc  );      end     =     clock  ();      qsort_time     +=     ((  double  )(  end     -     start  ))     /     CLOCKS_PER_SEC  ;      free  (  a  );      }      insertion_sort_time     /=     number_of_times  ;      merge_sort_time     /=     number_of_times  ;      merge_sort_and_insertion_sort_mix_time     /=     number_of_times  ;      qsort_time     /=     number_of_times  ;      printf  (  '  n  Time taken to sort:  n  '      '%-35s %f  n  '      '%-35s %f  n  '      '%-35s %f  n  '      '%-35s %f  nn  '        '(i)Insertion sort: '        insertion_sort_time        '(ii)Merge sort: '        merge_sort_time        '(iii)Insertion-mergesort-hybrid: '        merge_sort_and_insertion_sort_mix_time        '(iv)Qsort library function: '        qsort_time  );   }   int     main  (  int     argc       char     const     *  argv  [])   {      int     t  ;      scanf  (  '%d'       &  t  );      while     (  t  --  )      {      int     size       num_of_times  ;      scanf  (  '%d %d'       &  size       &  num_of_times  );      test_sorting_runtimes  (  size       num_of_times  );      }      return     0  ;   }   

   import     java.util.Scanner  ;   import     java.util.Arrays  ;   import     java.util.Random  ;   public     class   SortingAlgorithms     {      // Maximum element in array      static     final     int     MAX_ELEMENT_IN_ARRAY     =     1000000001  ;      public     static     void     main  (  String  []     args  )     {      Scanner     scanner     =     new     Scanner  (  System  .  in  );      int     t     =     scanner  .  nextInt  ();      for     (  int     i     =     0  ;     i      <     t  ;     i  ++  )     {      int     size     =     scanner  .  nextInt  ();      int     num_of_times     =     scanner  .  nextInt  ();      testSortingRuntimes  (  size       num_of_times  );      }      scanner  .  close  ();      }          static     int  []     generateRandomArray  (  int     n  )     {      // Generate an array of n random integers.      int  []     arr     =     new     int  [  n  ]  ;      Random     random     =     new     Random  ();      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )     {      arr  [  i  ]     =     random  .  nextInt  (  MAX_ELEMENT_IN_ARRAY  );      }      return     arr  ;      }      static     void     insertionSortAsc  (  int  []     a       int     start       int     end  )     {      // Perform an in-place insertion sort on a from start to end.      for     (  int     i     =     start     +     1  ;     i      <=     end  ;     i  ++  )     {      int     key     =     a  [  i  ]  ;      int     j     =     i     -     1  ;      while     (  j     >=     start     &&     a  [  j  ]     >     key  )     {      a  [  j     +     1  ]     =     a  [  j  ]  ;      j  --  ;      }      a  [  j     +     1  ]     =     key  ;      }      }      static     void     merge  (  int  []     a       int     start       int     end       int     mid  )     {      // Merge two sorted sublists of a.      // The first sublist is a[start:mid+1] and the second sublist is a[mid+1:end+1].      int  []     aux     =     new     int  [  end     -     start     +     1  ]  ;      int     i     =     start       j     =     mid     +     1       k     =     0  ;      while     (  i      <=     mid     &&     j      <=     end  )     {      if     (  a  [  i  ]      <=     a  [  j  ]  )     {      aux  [  k  ++]     =     a  [  i  ++]  ;      }     else     {      aux  [  k  ++]     =     a  [  j  ++]  ;      }      }      while     (  i      <=     mid  )     {      aux  [  k  ++]     =     a  [  i  ++]  ;      }      while     (  j      <=     end  )     {      aux  [  k  ++]     =     a  [  j  ++]  ;      }      System  .  arraycopy  (  aux       0       a       start       aux  .  length  );      }      static     void     mergeSort  (  int  []     a  )     {      // Perform an in-place merge sort on a.      mergeSortHelper  (  a       0       a  .  length     -     1  );      }      static     void     mergeSortHelper  (  int  []     a       int     start       int     end  )     {      // Recursive merge sort function.      if     (  start      <     end  )     {      int     mid     =     start     +     (  end     -     start  )     /     2  ;      mergeSortHelper  (  a       start       mid  );      mergeSortHelper  (  a       mid     +     1       end  );      merge  (  a       start       end       mid  );      }      }      static     void     insertionAndMergeSortCombine  (  int  []     a       int     start       int     end       int     k  )     {      /*    Perform an in-place sort on a from start to end.    If the size of the list is less than or equal to k use insertion sort.    Otherwise use merge sort.    */      if     (  start      <     end  )     {      int     size     =     end     -     start     +     1  ;      if     (  size      <=     k  )     {      insertionSortAsc  (  a       start       end  );      }     else     {      int     mid     =     start     +     (  end     -     start  )     /     2  ;      insertionAndMergeSortCombine  (  a       start       mid       k  );      insertionAndMergeSortCombine  (  a       mid     +     1       end       k  );      merge  (  a       start       end       mid  );      }      }      }      static     void     testSortingRuntimes  (  int     size       int     num_of_times  )     {      // Test the runtime of the sorting algorithms.      double     insertionSortTime     =     0  ;      double     mergeSortTime     =     0  ;      double     mergeSortAndInsertionSortMixTime     =     0  ;      double     qsortTime     =     0  ;      for     (  int     i     =     0  ;     i      <     num_of_times  ;     i  ++  )     {      int  []     a     =     generateRandomArray  (  size  );      int  []     b     =     Arrays  .  copyOf  (  a       a  .  length  );      long     start     =     System  .  currentTimeMillis  ();      insertionSortAsc  (  b       0       b  .  length     -     1  );      long     end     =     System  .  currentTimeMillis  ();      insertionSortTime     +=     end     -     start  ;      int  []     c     =     Arrays  .  copyOf  (  a       a  .  length  );      start     =     System  .  currentTimeMillis  ();      mergeSort  (  c  );      end     =     System  .  currentTimeMillis  ();      mergeSortTime     +=     end     -     start  ;      int  []     d     =     Arrays  .  copyOf  (  a       a  .  length  );      start     =     System  .  currentTimeMillis  ();      insertionAndMergeSortCombine  (  d       0       d  .  length     -     1       40  );      end     =     System  .  currentTimeMillis  ();      mergeSortAndInsertionSortMixTime     +=     end     -     start  ;      int  []     e     =     Arrays  .  copyOf  (  a       a  .  length  );      start     =     System  .  currentTimeMillis  ();      Arrays  .  sort  (  e  );      end     =     System  .  currentTimeMillis  ();      qsortTime     +=     end     -     start  ;      }      insertionSortTime     /=     num_of_times  ;      mergeSortTime     /=     num_of_times  ;      mergeSortAndInsertionSortMixTime     /=     num_of_times  ;      qsortTime     /=     num_of_times  ;      System  .  out  .  println  (  'nTime taken to sort:n'      +     '(i) Insertion sort: '     +     insertionSortTime     +     'n'      +     '(ii) Merge sort: '     +     mergeSortTime     +     'n'      +     '(iii) Insertion-mergesort-hybrid: '     +     mergeSortAndInsertionSortMixTime     +     'n'      +     '(iv) Qsort library function: '     +     qsortTime     +     'n'  );      }   }   

   import   time   import   random   import   copy   from   typing   import   List   # Maximum element in array   MAX_ELEMENT_IN_ARRAY   =   1000000001   def   generate_random_array  (  n  :   int  )   ->   List  [  int  ]:   #Generate a list of n random integers.   return   [  random  .  randint  (  0     MAX_ELEMENT_IN_ARRAY  )   for   _   in   range  (  n  )]   def   insertion_sort_asc  (  a  :   List  [  int  ]   start  :   int     end  :   int  )   ->   None  :   #Perform an in-place insertion sort on a from start to end.   for   i   in   range  (  start   +   1     end   +   1  ):   key   =   a  [  i  ]   j   =   i   -   1   while   j   >=   start   and   a  [  j  ]   >   key  :   a  [  j   +   1  ]   =   a  [  j  ]   j   -=   1   a  [  j   +   1  ]   =   key   def   merge  (  a  :   List  [  int  ]   start  :   int     end  :   int     mid  :   int  )   ->   None  :   #Merge two sorted sublists of a.   #The first sublist is a[start:mid+1] and the second sublist is a[mid+1:end+1].   aux   =   []   i   =   start   j   =   mid   +   1   while   i    <=   mid   and   j    <=   end  :   if   a  [  i  ]    <=   a  [  j  ]:   aux  .  append  (  a  [  i  ])   i   +=   1   else  :   aux  .  append  (  a  [  j  ])   j   +=   1   while   i    <=   mid  :   aux  .  append  (  a  [  i  ])   i   +=   1   while   j    <=   end  :   aux  .  append  (  a  [  j  ])   j   +=   1   a  [  start  :  end  +  1  ]   =   aux   def   _merge_sort  (  a  :   List  [  int  ]   start  :   int     end  :   int  )   ->   None  :   #Recursive merge sort function.   if   start    <   end  :   mid   =   start   +   (  end   -   start  )   //   2   _merge_sort  (  a     start     mid  )   _merge_sort  (  a     mid   +   1     end  )   merge  (  a     start     end     mid  )   def   merge_sort  (  a  :   List  [  int  ])   ->   None  :   #Perform an in-place merge sort on a.   _merge_sort  (  a     0     len  (  a  )   -   1  )   def   insertion_and_merge_sort_combine  (  a  :   List  [  int  ]   start  :   int     end  :   int     k  :   int  )   ->   None  :      '''    Perform an in-place sort on a from start to end.    If the size of the list is less than or equal to k use insertion sort.    Otherwise use merge sort.    '''   if   start    <   end  :   size   =   end   -   start   +   1   if   size    <=   k  :   insertion_sort_asc  (  a     start     end  )   else  :   mid   =   start   +   (  end   -   start  )   //   2   insertion_and_merge_sort_combine  (  a     start     mid     k  )   insertion_and_merge_sort_combine  (  a     mid   +   1     end     k  )   merge  (  a     start     end     mid  )   def   test_sorting_runtimes  (  size  :   int     num_of_times  :   int  )   ->   None  :   #Test the runtime of the sorting algorithms.   insertion_sort_time   =   0   merge_sort_time   =   0   merge_sort_and_insertion_sort_mix_time   =   0   qsort_time   =   0   for   _   in   range  (  num_of_times  ):   a   =   generate_random_array  (  size  )   b   =   copy  .  deepcopy  (  a  )   start   =   time  .  time  ()   insertion_sort_asc  (  b     0     len  (  b  )   -   1  )   end   =   time  .  time  ()   insertion_sort_time   +=   end   -   start   c   =   copy  .  deepcopy  (  a  )   start   =   time  .  time  ()   merge_sort  (  c  )   end   =   time  .  time  ()   merge_sort_time   +=   end   -   start   d   =   copy  .  deepcopy  (  a  )   start   =   time  .  time  ()   insertion_and_merge_sort_combine  (  d     0     len  (  d  )   -   1     40  )   end   =   time  .  time  ()   merge_sort_and_insertion_sort_mix_time   +=   end   -   start   start   =   time  .  time  ()   a  .  sort  ()   end   =   time  .  time  ()   qsort_time   +=   end   -   start   insertion_sort_time   /=   num_of_times   merge_sort_time   /=   num_of_times   merge_sort_and_insertion_sort_mix_time   /=   num_of_times   qsort_time   /=   num_of_times   print  (  f  '  n  Time taken to sort:  n  '   f  '(i)Insertion sort:   {  insertion_sort_time  }  n  '   f  '(ii)Merge sort:   {  merge_sort_time  }  n  '   f  '(iii)Insertion-mergesort-hybrid:   {  merge_sort_and_insertion_sort_mix_time  }  n  '   f  '(iv)Qsort library function:   {  qsort_time  }  n  '  )   def   main  ()   ->   None  :   t   =   int  (  input  ())   for   _   in   range  (  t  ):   size     num_of_times   =   map  (  int     input  ()  .  split  ())   test_sorting_runtimes  (  size     num_of_times  )   if   __name__   ==   '__main__'  :   main  ()   

   // Importing required modules   const     {     performance     }     =     require  (  'perf_hooks'  );   // Maximum element in array   const     MAX_ELEMENT_IN_ARRAY     =     1000000001  ;   // Function to generate a list of n random integers   function     generateRandomArray  (  n  )     {      return     Array  .  from  ({  length  :     n  }     ()     =>     Math  .  floor  (  Math  .  random  ()     *     MAX_ELEMENT_IN_ARRAY  ));   }   // Function to perform an in-place insertion sort on a from start to end   function     insertionSortAsc  (  a       start       end  )     {      for     (  let     i     =     start     +     1  ;     i      <=     end  ;     i  ++  )     {      let     key     =     a  [  i  ];      let     j     =     i     -     1  ;      while     (  j     >=     start     &&     a  [  j  ]     >     key  )     {      a  [  j     +     1  ]     =     a  [  j  ];      j     -=     1  ;      }      a  [  j     +     1  ]     =     key  ;      }   }   // Function to merge two sorted sublists of a   function     merge  (  a       start       end       mid  )     {      let     aux     =     [];      let     i     =     start  ;      let     j     =     mid     +     1  ;      while     (  i      <=     mid     &&     j      <=     end  )     {      if     (  a  [  i  ]      <=     a  [  j  ])     {      aux  .  push  (  a  [  i  ]);      i     +=     1  ;      }     else     {      aux  .  push  (  a  [  j  ]);      j     +=     1  ;      }      }      while     (  i      <=     mid  )     {      aux  .  push  (  a  [  i  ]);      i     +=     1  ;      }      while     (  j      <=     end  )     {      aux  .  push  (  a  [  j  ]);      j     +=     1  ;      }      for     (  let     i     =     start  ;     i      <=     end  ;     i  ++  )     {      a  [  i  ]     =     aux  [  i     -     start  ];      }   }   // Recursive merge sort function   function     _mergeSort  (  a       start       end  )     {      if     (  start      <     end  )     {      let     mid     =     start     +     Math  .  floor  ((  end     -     start  )     /     2  );      _mergeSort  (  a       start       mid  );      _mergeSort  (  a       mid     +     1       end  );      merge  (  a       start       end       mid  );      }   }   // Function to perform an in-place merge sort on a   function     mergeSort  (  a  )     {      _mergeSort  (  a       0       a  .  length     -     1  );   }   // Function to perform an in-place sort on a from start to end   function     insertionAndMergeSortCombine  (  a       start       end       k  )     {      if     (  start      <     end  )     {      let     size     =     end     -     start     +     1  ;      if     (  size      <=     k  )     {      insertionSortAsc  (  a       start       end  );      }     else     {      let     mid     =     start     +     Math  .  floor  ((  end     -     start  )     /     2  );      insertionAndMergeSortCombine  (  a       start       mid       k  );      insertionAndMergeSortCombine  (  a       mid     +     1       end       k  );      merge  (  a       start       end       mid  );      }      }   }   // Function to test the runtime of the sorting algorithms   function     testSortingRuntimes  (  size       numOfTimes  )     {      let     insertionSortTime     =     0  ;      let     mergeSortTime     =     0  ;      let     mergeSortAndInsertionSortMixTime     =     0  ;      let     qsortTime     =     0  ;      for     (  let     _     =     0  ;     _      <     numOfTimes  ;     _  ++  )     {      let     a     =     generateRandomArray  (  size  );      let     b     =     [...  a  ];      let     start     =     performance  .  now  ();      insertionSortAsc  (  b       0       b  .  length     -     1  );      let     end     =     performance  .  now  ();      insertionSortTime     +=     end     -     start  ;      let     c     =     [...  a  ];      start     =     performance  .  now  ();      mergeSort  (  c  );      end     =     performance  .  now  ();      mergeSortTime     +=     end     -     start  ;      let     d     =     [...  a  ];      start     =     performance  .  now  ();      insertionAndMergeSortCombine  (  d       0       d  .  length     -     1       40  );      end     =     performance  .  now  ();      mergeSortAndInsertionSortMixTime     +=     end     -     start  ;      start     =     performance  .  now  ();      a  .  sort  ((  a       b  )     =>     a     -     b  );      end     =     performance  .  now  ();      qsortTime     +=     end     -     start  ;      }      insertionSortTime     /=     numOfTimes  ;      mergeSortTime     /=     numOfTimes  ;      mergeSortAndInsertionSortMixTime     /=     numOfTimes  ;      qsortTime     /=     numOfTimes  ;      console  .  log  (  `nTime taken to sort:n(i)Insertion sort:   ${  insertionSortTime  }  n(ii)Merge sort:   ${  mergeSortTime  }  n(iii)Insertion-mergesort-hybrid:   ${  mergeSortAndInsertionSortMixTime  }  n(iv)Qsort library function:   ${  qsortTime  }  n`  );   }   // Main function   function     main  ()     {      let     t     =     parseInt  (  prompt  (  'Enter the number of test cases: '  ));      for     (  let     _     =     0  ;     _      <     t  ;     _  ++  )     {      let     size     =     parseInt  (  prompt  (  'Enter the size of the array: '  ));      let     numOfTimes     =     parseInt  (  prompt  (  'Enter the number of times to run the test: '  ));      testSortingRuntimes  (  size       numOfTimes  );      }   }   // Call the main function   main  ();