**You are being recorded and transcribed.**

*Approximate overview*

- Administrivia
- Check in on Wednesday’s class
- Some notes on sorting
- Testing sorting algorithms
- Loop invariants

- Registration preview

- Friday, 2024-03-15, 11pm, Third set of LAs.
- Mostly posted.
- Let me know if any look wrong.
- Let me know if you’d like to see any others posted.
- Grading is still on my priority queue, near the front.

Academic/Scholarly

Cultural

- Friday at 4pm in the Global Living Room.
*Middle of Everywhere*.- I don’t know whether or not that’s happening.

Peer

Wellness

Misc

- You are awesome. Please take care of yourselves.
- And don’t get me fired for sharing information with you.

What did you learn?

- Merge sort.
- Merge algorithm: Merge two sorted lists (or subarrays)
- Merge sort - If the list has more than one element, divide the unsorted list in half, sort the two halves, merge them together.
- Can I merge in place (e.g., [1 ,4, 6, 9, 2, 3, 5, 8])?
- Nope. I need to make a helper array to copy things into.
- This is a disadvantage of merge sort: It requires O(n) extra space.

- Do I have to use merge sort when I sort each subarray?
- Nope.

- How do you prove it correct?
- Experimentally, we run tests
- We could do a proof. With invariants.

- Is merge sort stable?
- Stable: If there are two “equal” elements, they maintain their order. (That may have been in the reading.)
- No: It depends a bit on how you merge.
- Can we decide on an approach that maintains stability? Yes! When we merge, always take the element from the left array first.

- Stability
- We all sort all the time.
- MSort: Divide the cards into two piles: Sorted and Unprocessed. For each card in unprocessed, put it into the right place in sorted.
- ASort: Similar, with a probabilistic (ML-based) approach for finding the right location.
- Insertion sort

- Analysis of insertion sort (incorrect)
- We have to insert
`n`

cards from unprocessed list into the sorted list. - Finding the right location takes O(logn) time because we can use binary search.
- Inserting it into that position is constant time.
- This algorithm is O(nlogn).

- We have to insert
- Why is this incorrect? (Hint: It may be O(nlogn) in the physical world,
but not in the computer world.)
- If the data are stored in an array, it will take O(n) to insert, not O(1) because you have to shift stuff over to make room.
- If the data are stored in a link list, it only takes O(1) to insert once you’ve found the spot, but be can’t use binary search on lists, since binary search requires quick access based on index.

- Analysis: O(n^2) for arrays because O(n) to insert.
- Analysis: O(n^2) for lists because O(n) to find.
- Reminder: Once you’ve correctly analyzed an algorithm, you have two questions
to ask:
- Can I do better?
- If not: Can I prove that I can’t do better?

- Detour: For the “can I prove”, Travelling Salescritter Problem
- Given a set of
`n`

cities, find the shortest path connecting them all. - Easy solution: Make a list of all the paths, take the shortest.
- Unfortunately, there are O(n!) paths, which grows way too quickly.

- Given a set of
- In 301, you’ll get to consider whether a sorting algorithm can be faster than O(nlogn). (Preview: Not for a compare/swap algorithm.)
- In 341, you’ll get to explore questions like TSP.
- For insertion sort’s “can I do better”
- Design a different algorithm
- Design a new data structure, one that has both quick insertion and quick searching.

- A better data structure: The binary search tree
- A binary tree is a structure in which you have a node (with a value), left subtree, and right subtree.
- Usually the left subtree has values less than the node and the right subtree has values greater than the node.
- Both left and right subtrees have the same property.

- If the tree is mostly balanced (that is, we have left and right subchildren at most levels; the two subtrees are about the same size ), the number of levels is O(logn).
- Search is O(logn)
- Insert is O(logn)
- Maintaining the property is hard.
- We will return to this issue in a few weeks.

You’ve written a sorting algorithm. Proofs are hard. You want tests. What kind of “write lots of tests” algorithm would you write?

- Systematically
- Random

Systematically

- Use for loops to build arrays of different sizes
- For each size array

Random

- Use a for loop to build arrays of different sizes
- Sort each
- And make sure it’s in order AND a permutation of the original

Sam’s Sorting algorithm (which gives you an array in order)

```
public static

More ideas

- Start with a sorted array.
- Permute it (or permute a copy) [shuffle; rearrange]
- Sort the permutation
- Compare the two arrays.

Even more

- Start with a sorted array.
- Sort it.
- See if it’s the same. (Some non-stable sorting algorithms will rearrange equal elements, so for this, we want to ensure that equal elements are treated as equal.)

Whoops!