Activity: Merge and Quick Sort

Learning Objectives:

Understand how to merge two sorted lists
Trace through merge and quick sort algorithms
Explain why these algorithms allow for \(n\ log_2\ n\) performance
Analyze and compare the performance of sorting algorithms

Time to Complete: 50 minutes

To Receive Credit: Submit individual PDF to Canvas

Instructions:

For these activities, follow the steps closely. Your goal is to complete all parts of the activity within the time provided.

If a section is hidden behind a "Continue" button, you should make sure that you have completed the previous sections and answered any questions before moving on. Do not skip ahead or reveal any solution until you have completed the previous steps.

Collaboration Encouraged

I encourage you to work with a partner or in a small group (no more than three) for in-class activities! Feel free to divvy up roles, compare solutions, and learn from each other.

If the assignment requires you to submit your work, make sure to include the names of all team members in the submission.

Your Name(s):

Part 1: Merging Lists (Conecptual)

(10 minutes)

Imagine you have two equal-sized lists, a and b:
- Let's represent them in pseudocode (aka Python lol) as follows:
```
a = [1, 5, 6, 7]
b = [2, 3, 4, 8]
```
- Are each of these lists sorted?
  
  Solution
  
  Yes, both lists are sorted. For instance, all the elements in a are in ascending order.

Now, let's think about if we wanted to combine both sorted lists into one big sorted list.
- One way to do this is to concatenate the lists and then sort the result.
```
c = a + b
c.selectionSort()
```
  - If we used selectionSort, this would take \(\Theta(n^2)\) time.
- Does this approach take advantage of the fact that both sub-lists are sorted?
  
  Solution
  
  No, this approach does not take advantage of the fact that both sub-lists are already sorted.
  
  Can we do better?

There must be an approach that can merge two sorted sub-lists more efficiently!
- Let's think for about how we can leverage the fact that both a and b are sorted.
- Let's start by comparing the first elements of each list:
```
a: [1, 5, 6, 7]
b: [2, 3, 4, 8]
```
- Which element is smaller, a[0] or b[0]?
  
  Solution
  
  The element a[0] is smaller than b[0].
- What should be the first element of the merged list (we'll call this c)?
  
  Solution
  
  The first element of the merged list c should be a[0], or the element 1.

Okay, let's continue merging the two lists.
- We've already added 1 to the merged list, so let's remove it from a.
- Now, consider the following:
```
a: [5, 6, 7]
b: [2, 3, 4, 8]
c: [1]
```
- Now, which element is smaller, a[0] or b[0]?
  
  Solution
  
  The element b[0] is smaller than a[0].
- What is the value of the next element to add to the merged list, c?
  
  Solution
  
  The next value to add to the merged list c is 2, or b[0].

Let's continue merging the two lists.
- We can remove 2 from b.
- Now, consider the following:
```
a: [5, 6, 7]
b: [3, 4, 8]
c: [1, 2]
```
- Which element is smaller, a[0] or b[0]?
  
  Solution
  
  The element b[0] is smaller than a[0].
- What is the value of the next element to add to the merged list, c?
  
  Solution
  
  The next value to add to the merged list c is 3, or b[0].

Do you see the pattern here?
- Compare the first elements of each list. Add the smaller element to the merged list.
  - We can repeat this process until one of the lists is empty.
  - Then, we can add the leftover elements to the merged list.
- Assume we continue this process until both a and b are empty.
  - Think about counting the number of times we compare elements in a and b.
- Consider the following worst-case input:
```
a = [1, 3, 5, 7]
b = [2, 4, 6, 8]
```
- How many times do we compare elements in a and b in this case? (enter a number)
  
  Solution
  
  In this case, we compare elements 7 times.
  
  1. 1 vs 2
  2. 3 vs 2
  3. 3 vs 4
  4. 5 vs 4
  5. 5 vs 6
  6. 7 vs 6
  7. 7 vs 8
  
  Hmm, that's a lot of comparisons, but no more than the total number of elements!

Let's generalize. Let \(n\) be the total number of elements in both lists. (So each equally-sized list has \(n/2\) elements.)
- Again, let's count comparisons (between elements in a and b).
- What is the (worst-case) Big-Theta time complexity of this merging process?
  
  Solution
  
  \(\Theta(n)\), since there would be \(n - 1\) comparisons in the worst case.

Here's an example of the best-case scenario for merging two sorted lists:
```
a = [1, 2, 3, 4]
b = [5, 6, 7, 8]
```
- How many comparisons would be needed in this example? (enter a number)
  
  Solution
  
  In the best-case scenario, we would need 4 comparisons.
  
  1. 1 vs 5
  2. 2 vs 5
  3. 3 vs 5
  4. 4 vs 5
  
  Hmm, that's conveniently the same as the number of elements in one list!
- Generalize: What is the Big-Theta time complexity of the best-case scenario?
  
  Solution
  
  \(\Theta(n)\), since there would be \(n/2\) comparisons in the best case.

In general, assuming equal-sized lists, if \(n\) represents the total number of elements in both lists:
- Worst-case comparisons: \(W(n) = n - 1\)
  - Time complexity: \(\Theta(n)\)
- Best-case comparisons: \(B(n) = n/2\)
  - Time complexity: \(\Theta(n)\)
Performance for Non-Equal Sized Lists

If the lists are not equal in size, the number of comparisons would be different. However, the time complexity would still be \(\Theta(n)\).

For non-equal-sized lists, if \(n\) represents the number of elements in a and \(m\) represents the number of elements in b:
- Worst-case comparisons: \(W(n, m) = n + m - 1\)
- Best-case comparisons: \(B(n, m) = \min(n, m)\)

Takeaway

Merging two sorted lists can be done in \(\Theta(n)\) time, where \(n\) is the total number of elements in both lists.

It's important to note (and remember) how the merge works even with one element in each list! That is the smallest unit of merging.

This is a conceptual version of merge that is used in the Merge Sort algorithm. We will look at the Java implementation in the next section, which only uses two arrays, instead of multiple lists.

Part 2: Merge Sort

(20 minutes)

Now that you understand how the merge operation works, let's look at the code for Merge Sort.
- First, the mergeSorter method takes in an array to sort, creates a temporary array, and calls a recursive method, mergesort, to perform the sorting:
```
public static void mergeSorter(int[] items) {
    int[] temp = new int[items.length];
    mergesort(items, temp, 0, items.length - 1);
}
```

The mergesort method is where the actual sorting happens.

The method takes in the array (to sort), the temporary array, and the left and right indices of a sub-array:

It only sorts the sub-array indicated by the left and right indices (inclusive).
The temporary array is used by merge() -- don't worry about it for now.

private static void mergesort(int[] items, int[] temp, 
                              int left, int right) {

    if (left == right) {
        return; // Sub-array has one element
    }

    int mid = (left + right) / 2; 

    mergesort(items, temp, left, mid);       // Recursive call A
    mergesort(items, temp, mid + 1, right);  // Recursive call B

    merge(items, temp, left, mid, right);    // Merge the two sorted halves
}

Understanding the Code

First, let's think about the following array of eight elements:
```
int[] items = {3, 5, 1, 7, 8, 6, 2, 4};
```
- Imagine we call mergeSorter(items), which then calls mergesort():
  - What indices would left and right point to?
    
    Solution
    
    The values of left and right would be 0 and 7, respectively.
  - What index would mid point to?
    
    Solution
    
    The value of mid would be 3.

Now, think about the recursive calls:
- How many recursive calls are present in mergesort()?
  
  Solution
  
  2 recursive calls are present in this method, labeled A and B.
- In recursive call A, what would be the left and right indices?
  
  Solution
  
  The values of left and right would be 0 (left) and 3 (mid), respectively.
- In recursive call B, what would be the left and right indices?
  
  Solution
  
  The values of left and right would be 4 (mid + 1) and 7, respectively.

So in our first call to mergesort, we first logically split the array in two:
- The left half (indices 0 to 3): {3, 5, 1, 7}
- The right half (indices 4 to 7): {8, 6, 2, 4}
Then we recursively call mergesort for each half.
Trust that the recursive calls work. Each call should fully sort its half of the array. Don't actually trace through the recursive calls.
- What values would be in the left half after recursive call A?
  
  Solution
  
  The sorted left half would be {1, 3, 5, 7}.
- What values would be in the right half after recursive call B?
  
  Solution
  
  The sorted right half would be {2, 4, 6, 8}.

So, if the left half and the right half are now sorted sub-arrays, our whole array would look like this:
```
items: {1, 3, 5, 7,    2, 4, 6, 8}
```
- Again, what indices would left, mid, and right point to, for the merge operation?
  
  Solution
  
  The values of left, mid, and right would be 0, 3, and 7, respectively.

Merge Operation

Let's take a look at the merge operation now. How we accomplish this in Java is by copying values to a temporary array and then copy them back to the original array.

The merge method takes in the array, the temporary array, and the left, mid, and right indices:

private static void merge(int[] items, int[] temp, 
                          int left, int mid, int right) {

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

    // Merge the two subarrays

    int l = left;    // Where we are in the left subarray
    int r = mid + 1; // Where we are in the right subarray

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

I want you to have a clear understanding of how this method works.

Don't have physical objects?

You can use a virtual deck of cards online: Deck of Cards
- Using cards, pieces of paper, dice, or other objects, arrange the following numbers in an array like so:
  
  Index 0 1 2 3 4 5 6 7
  
  Value 1 3 5 7 2 4 6 8
- Next, let's pretend to "copy" the values to the temporary array by moving all the items down to below the array:
  
  Index 0 1 2 3 4 5 6 7
  
  Value (empty)
  
  1 3 5 7 2 4 6 8

Now, trace through the code starting at the // Merge the two subarrays line.
- You will need to get out three pens, pieces of paper, or other markers for each index:
  - One for the l index (current position in the left subarray)
  - One for the r index (current position in the right subarray)
  - One for the curr index (current position in the merged array)
- Designate one person to count the number of comparisons betweeen array items (marked with "COUNT THIS").
- When you assign a value to items[curr], move the item from the temporary array up to the corresponding location in the items array.
After tracing, answer the following questions:
- What does the array look like after the merge operation?
  
  Solution
  
  The array would look like this: {1, 2, 3, 4, 5, 6, 7, 8}.
- How many comparisons between array elements are made in this merge operation?
  
  Solution
  
  There are 7 comparisons made in this merge operation.
- Does this code implement the conceptual merge operation we discussed earlier?
  
  Solution
  
  Yes, this code implements the conceptual merge operation we discussed earlier.

Performance Analysis

Let's go back to the bigger picture:

private static void mergesort(int[] items, int[] temp, 
                              int left, int right) {

    if (left == right) {
        return; // Sub-array has one element
    }

    int mid = (left + right) / 2; 

    mergesort(items, temp, left, mid);       // Recursive call A
    mergesort(items, temp, mid + 1, right);  // Recursive call B

    merge(items, temp, left, mid, right);    // Merge the two sorted halves
}

First, can you think about the algorithm and describe how merge sort works in your own words?
- How does merge sort work?
  
  Solution
  
  Merge sort is a "divide-and-conquer" algorithm that recursively divides an array into two halves, sorts each half, and then merges the two sorted halves.
  
  At each level of recursion, the array is divided into two halves until each sub-array has one element. There is no need to continue calling mergesort on a sub-array with one element, since an array with one element is already sorted.
  
  Then, the sub-arrays are merged back together in sorted order. Then we return to the previous level of recursion and merge the two sorted halves again. And again. And again, until the entire array is sorted.

Now, let's analyze the performance of merge sort. We will count the number of comparisons between elements as before.
- Let n represent the number of elements in the initial array.
- Let's consider a worst-case analysis. Use \(W(n)\) to represent this.
- Remember that merge() incurs \(W_{merge}(n) = n - 1\) comparisons in the worst-case.
Let's determine our base case:
- What value of n will stop the recursion in mergesort()?
  
  Solution
  
  The recursion will stop when n = 1.
- What is the number of array comparisons made by mergesort() when this is the case?
  
  Solution
  
  When n = 1, there are 0 comparisons made by mergesort().
- Using these facts, write an initial condition for our recurrence:
  
  Solution
  
  \(W(1) = 0\)

Now, let's develop the recurrence relation:
- Again, how many comparisons are made by merge() in the worst case?
  
  Solution
  
  In the worst case, merge() makes \(n - 1\) comparisons.
- How many recursive calls are present in mergesort()?
  
  Solution
  
  Two recursive calls are present in mergesort().
- What is the size of the sub-arrays given to each recursive call?
  - Assume \(n\) is a perfect power of 2.
  Solution
  
  The size of the sub-arrays is \(n/2\) in each recursive call.
- Using these facts, write a recurrence relation (\(W(n) =\) ...) for the number of comparisons made by mergesort():
  
  Solution
  
  \(W(n) = 2W(n/2) + (n - 1)\)

Our full recurrence is as follows:

\(W(1) = 0\)
\(W(n) = 2W(\frac{n}{2}) + (n - 1)\)
We will solve this recurrence together on the board.
- You can move on to the next section.
- Or, you can also attempt to solve the recurrence on your own.
  - Here's some useful facts:
    
    \(\sum_{i=0}^{k} 2^i = 2^{k+1} - 1\)
    
    \(\sum_{i=0}^{k} (a + b) = \sum_{i=0}^{k} a + \sum_{i=0}^{k} b\)
Hint

Your answer should be \(\Theta(n \log n)\).

Part 3: Quicksort

(20 minutes)

Now, let's take a quick look at Quicksort. Why is it called "Quicksort"?
- OpenDSA: "It's the fastest known general-purpose in-memory sorting algorithm in the average case."

Partitioning

In order to understand Quicksort, we need to understand how "partitioning" works:

private static int partition(int[] items, int left, int right) {

    int pivotindex = (left + right) / 2; // Pick the middle element
    int pivot = items[pivotindex];       // Value of the pivot

    swap(items, pivotindex, right);      // Stick pivot at end (temporarily)
    pivotindex = right;                  // Remember where it is.
    right--;                             // Don't include pivot in partition

    // Move bounds inward until they meet
    while (left <= right) {
        while (items[left] < pivot) {
            left++;
        }

        while ((right >= left) && (items[right] >= pivot)) {
            right--;
        }

        if (right > left) {
            swap(items, left, right);    // Swap out-of-place values
        }
    }

    swap(items, left, pivotindex);       // Put pivot in place

    return left; // Return destination index of pivot
}

Let's start by tracing through the partitioning process:
- Arrange the following six values in your array:
  
  Index 0 1 2 3 4 5
  
  Value 6 2 4 5 3 1
- Let's start with left = 0 and right = 5.
  - Use a pen or paper to track where left and right are pointing.
- What is the pivotindex for this array?
  
  Solution
  
  The pivotindex would be 2.
- What is the value of the pivot?
  
  Solution
  
  The value of the pivot would be 4.
- Trace through the partitioning process, moving the left and right as needed.
After tracing, answer the following questions:
- What does the array look like after the partitioning process?
  
  Solution
  
  The array would look like this: {3, 2, 1, 4, 6, 5}.
- What index is the final position of the pivot value?
  
  Solution
  
  The final position of the pivot would be index 3.
- Look at all the values to the left of the pivot. What do you notice?
  
  Solution
  
  All the values to the left of the pivot are less than the pivot value.
- Look at all the values to the right of the pivot. What do you notice?
  
  Solution
  
  All the values to the right of the pivot are greater than or equal to the pivot value.
  
  The pivot is in the correct position!

To make sure you fully understand, let's repeat the process with the following values in your array (should be the same as you left it):

Index 0 1 2 3 4 5

Value 3 2 1 4 6 5
- This time, let's start with left = 0 and right = 2.
  - Now, we're working with only the left side of the array.
- What is the pivotindex now?
  
  Solution
  
  The pivotindex would be 1.
- What is the value of the pivot?
  
  Solution
  
  The value of the pivot would be 2.
- Again, trace through the partitioning process, moving the left and right markers as needed.
What does the array look like after the partitioning process?

Hint

You should not be modifying any values from index 3 to 5.

Solution

The array would look like this: {1, 2, 3, 4, 6, 5}.

Let's do one more check. Assume you have the array items = {1, 2, 3, 4, 6, 5}
- If I called partition(items, 4, 5), what would the array look like after the partitioning process?
  - Here, we are only working with the right side of the array.
  - You should not need to trace through the code -- develop an intuition for how the partition works.
  Solution
  
  The array would look like this: {1, 2, 3, 4, 5, 6}

Hey, everything is sorted now! This is the basis of Quicksort.

Partitioning

To summarize the partitioning process:

The pivot is chosen as the middle element.
- (This is just one way to choose the pivot.)
The pivot is moved to the end of the array.
The left and right bounds move inward:
1. We find the first element on the left that is greater than or equal to the pivot.
2. We find the first element on the right that is less than the pivot.
3. If the right element is greater than the left element, we swap them.
  - Aka, if the elements are on the wrong side of the pivot, we swap them.
Finally, the pivot is placed in the correct position.
- Its position will depend on how many values are less than the pivot.

Quicksort Algorithm

Now, let's bring it all together. Take a look at the code for Quicksort:

public static void quicksorter(int[] items) {
    quicksort(items, 0, items.length - 1);    
}

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

    // curr will be the final position of the pivot item.
    int curr = partition(items, left, right);

    quicksort(items, left, curr - 1);  // Sort left partition
    quicksort(items, curr + 1, right); // Sort right partition
}

The quicksorter method is the entry point for Quicksort. It calls the recursive helper method quicksort with the initial bounds.
The quicksort method is where the actual sorting happens. It calls the partition method to find the final position of the pivot.
- The method then recursively calls quicksort on the left and right partitions.

Original OpenDSA Version

The method above is slightly simplified for clarity. The original OpenDSA version is below:

private static void quicksort(int[] items, int left, int right) {
    // curr will be the final position of the pivot item.
    int curr = partition(items, left, right);

    if ((curr - left) > 1) {
        quicksort(items, left, curr - 1); // Sort left partition
    }

    if ((right - curr) > 1) {
        quicksort(items, curr + 1, right); // Sort right partition
    }
}

Let's do a little analysis of the Quicksort algorithm:
- First, realize that you will need two initial conditions, because we could end up with a sub-array of size 0 or 1. How many operations would be needed in these cases?
- State our initial condition(s):
  
  Solution
  
  \(T(0) = 0\) \(T(1) = 0\)
- How many recursive calls are present?
  
  Solution
  
  There are two recursive calls.

The choice of the pivot can also affect the performance of Quicksort.
- We used the middle element as the pivot in our implementation. Other choices include the first element, the last element, or a random element.
- If the value of the pivot is always (unluckily) the smallest or largest element, we get the worst-case performance.
  - Think: if the pivot is the largest item, and there are n items...
    
    How many items are less than the pivot?
    
    Solution
    
    There are n-1 items less than the pivot. Meaning we make a single recursive call of quicksort(n-1).
    
    If this happens again, then we make another recursive call of quicksort(n-2). This repeats a total of n times, so we would have a max recursive depth of \(n\).
- If the pivot is always (luckily) the median, we get the best-case performance.
  - Think: if the pivot is the median item, and there are n items...
    
    How many items are less than the pivot? Assume n is perfectly divisible.
    
    Solution
    
    We would split the array perfectly down the middle. There are n/2 items less than the pivot, and n/2 items greater than the pivot.
    
    Think about if we repeated this process for each half... we would split the array into ¼ths. And then ⅛ths. And so on. So we would have a max recursive depth of \(log_2\ n\).

Performance Analysis

The performance of Quicksort depends on the performance of the partition() method.
- We are using an implementation of "Hoare's partitioning scheme", which is easier to understand, but not the most efficient.
  - Our implementation can take 2n-1 comparisons for odd-sized arrays, and 2n-2 comparisons for even-sized arrays. (assuming worst-case)
- "Lomuto's partitioning scheme" is simpler and takes n-1 comparisons in all cases.

Consider the code again:

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

    // curr will be the final position of the pivot item.
    int curr = partition(items, left, right);

    quicksort(items, left, curr - 1);  // Sort left partition
    quicksort(items, curr + 1, right); // Sort right partition
}

Perform a best-case analysis, where we are able to perfectly split the array down the middle into two equal sub-problems.
- Assume that the partition() method incurs \(T_{partition}(n) = n - 1\) operations.
- Write a recurrence that expresses the best-case number of comparisons. Include initial conditions.
  
  Solution
  
  \(B(0) = 0\)
  \(B(1) = 0\)
  \(B(n) = (n - 1) + 2 * B(n/2)\)

Perform a worst-case analysis, where we get unlucky and have to perform a single recursive call with n-1 input size every time.
- Write a recurrence that expresses the worst-case number of comparisons. Include initial conditions.
  
  Solution
  
  \(W(0) = 0\)
  \(W(1) = 1\)
  \(W(n) = (n - 1) + W(n - 1)\)

Part 4: Quicksort Analysis

(remaining time)

Solve the recurrence for worst-case number of comparisons:

\(W(0) = 0\)
\(W(1) = 1\)
\(W(n) = (n - 1) + W(n - 1)\)

Hint

You should get something that is \(\Theta(n^2)\).

Solution

\(W(n) = \frac{n (n - 1)}{2}\)
Solve the recurrence for best-case number of comparisons:

\(B(0) = 0\)
\(B(1) = 0\)
\(B(n) = (n - 1) + 2 * B(n/2)\)

Hint

You should get something that is \(\Theta(n * log_2\ n)\).

Solution

\(B(n) = n * log_2\ n - n + 1\)
Is Quicksort stable? Trace through the following:

0 1 2 3 4

4 1 2 1 3
- Use different colored 1's and keep track of which color came first.
- Is quicksort stable? Why or why not?
  
  Solution
  
  Quicksort is not stable. The relative order of equal elements can change during the sorting process.
Go look at the OpenDSA visualizer for Quicksort.
- Try some random values and step through the visualization.

Submission

For these activities, you will typically submit a PDF report to Canvas. First, click the "Export as PDF" button below.

Then, submit the PDF to Canvas. Everyone must submit their own copy to receive credit.

Index	0	1	2	3	4	5	6	7
Value	(empty)
	1	3	5	7	2	4	6	8