So far…

• Insertion sort $\mathrm{\Theta }(n^2)$ worst and average case.
• Selection sort $\mathrm{\Theta }(n^2)$ worst and average case.
• Is this good?

Merging…

Mergesort

   private static void mergeSort(int[] numbers, int start, int end) {
      
      if (start < end) {
         
         int mid = (start + end) / 2;

         mergeSort(numbers, start, mid);
         mergeSort(numbers, mid + 1, end);
            
         merge(numbers, start, mid, end);
      }
   }

Socrative… Given that merge requires $f(n)$ comparisons to merge $n$ elements, provide a recurrence relation describing the worst-case number of comparisons performed by mergesort.

Merge

   private static void merge(int[] numbers, int start, int mid, int end) {
      int mergedSize = end - start + 1;            // Size of merged partition
      int[] mergedNumbers = new int[mergedSize];   // Dynamically allocate temporary
                                                   //    array for merged numbers
      int mergePos = 0;                            // Position to insert merged number
      int leftPos = start;                         // Initialize left partition position
      int rightPos = mid + 1;                      // Initialize right partition position
      
      while (leftPos <= mid && rightPos <= end) {
         if (numbers[leftPos] <= numbers[rightPos]) {
            mergedNumbers[mergePos] = numbers[leftPos];
            leftPos++;
         }
         else {
            mergedNumbers[mergePos] = numbers[rightPos];
            rightPos++;
         }
         mergePos++;
      }
      
      while (leftPos <= mid) {
         mergedNumbers[mergePos] = numbers[leftPos];
         leftPos++;
         mergePos++;
      }
   
      while (rightPos <= end) {
         mergedNumbers[mergePos] = numbers[rightPos];
         rightPos++;
         mergePos++;
      }
   
      // Copy merged numbers back to numbers
      for (mergePos = 0; mergePos < mergedSize; mergePos++) {
         numbers[start + mergePos] = mergedNumbers[mergePos];
      }
   }

Socrative… How many comparisons (between keys) are performed by merge in the worst case?

Mergesort Analysis

$W(1)=0$

$W(n)=n-1+2W(\frac{n}{2})$

Tree method…

Mergesort Analysis

Now we can write down the overall sum: $$\sum _{j=0}^{i}n-2^j$$

$i$ is determined by the initial condition…

$n/2^i=1$

$i={\log }_{2}n$

Substituting: $\sum _{j=0}^{{\log }_{2}n}n-2^j$

Mergesort Analysis

Useful fact: $\sum _{j=0}^n{2}^j=2^{n+1}-1$

$$\sum _{j=0}^{{\log }_{2}n}n-2^j$$ $$=\sum _{j=0}^{{\log }_{2}n}n-\sum _{j=0}^{{\log }_{2}n}{2}^j$$ $$=n({\log }_{2}n+1)-\sum _{j=0}^{{\log }_{2}n}{2}^j$$ (Apply useful fact.) $$=n({\log }_{2}n+1)-(2^{{\log }_{2}n+1}-1)$$ $$=n{\log }_{2}n+n-(2n-1)$$ $$=n{\log }_{2}n-n+1$$

What about assignments?

Repeat the analysis for assignments…