So far…

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

Merging…

Mergesort

  private static void mergesort(int[] items, int[] temp, 
                                int left, int right) {
    if (left == right) {
      return;
    }

    int mid = (left + right) / 2; 

    mergesort(items, temp, left, mid); 
    mergesort(items, temp, mid + 1, right); 

    merge(items, temp, left, mid, right);
  }

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[] items, int[] temp, 
                            int left, int mid, int right) {

    for (int i = left; i <= right; i++) {
      temp[i] = items[i];// Copy subarray to temp
    }

    int i1 = left;
    int i2 = mid + 1;
    for (int curr = left; curr <= right; curr++) {
      if (i1 == mid + 1) { // Left subarray exhausted
        items[curr] = temp[i2++];
      } else if (i2 > right) { // Right subarray exhausted
        items[curr] = temp[i1++];
      } else if (temp[i1] <= temp[i2]) { // Get smaller value (COUNT THIS!)
        items[curr] = temp[i1++];
      } else {
        items[curr] = temp[i2++];
      }
    }
  }

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…