Sorting Exercise

1. Insertion Sort - Show the array after each pass of insertion sort:
             45  23  67  89  12  34  56  21

Pass 1:     ______________________________________________________
      
Pass 2:     ______________________________________________________
     
Pass 3:     ______________________________________________________
      
Pass 4:     ______________________________________________________
      
Pass 5:     ______________________________________________________
      
Pass 6:     ______________________________________________________
      
Pass 7:     ______________________________________________________
      
How many passes are required to sort an array of n elements? _______
2. Selection Sort - Show the array after each pass of selection sort:
             45  23  67  89  12  34  56  21

Pass 1:     ______________________________________________________
      
Pass 2:     ______________________________________________________
     
Pass 3:     ______________________________________________________
      
Pass 4:     ______________________________________________________
      
Pass 5:     ______________________________________________________
      
Pass 6:     ______________________________________________________
      
Pass 7:     ______________________________________________________
      
How many passes are required to sort an array of n elements? _______

3. Show the "split" and "merge" phases below used to sort the given array using Merge Sort:

                          45  23  67  89  12  34  56  21
Split 1:       ___________________________         ___________________________
      
Split 2:     _____________   ______________      ______________   _____________
  
Split 3:   _____   ______   ______   ______     ______   ______   ______   ______

Merge 1:     _____________   ______________      ______________   _____________
  
Merge 2:       ___________________________         ___________________________

Merge 3:           _______________________________________________________

How many split phases are required to sort an array of n elements?  ________