Sorting: Selection, Insertion, & Merge

What is the theoretical lower bound for any comparison-based sorting algorithm?

\Omega(N \log N)

This is the "speed limit" for sorting. It means that for a large input of size N, any algorithm that relies on comparing elements will require, in its worst-case scenario, a number of comparisons that grows at least as fast as N \log N.

What is the core idea behind the \Omega(N \log N) lower bound proof?

The proof uses a decision tree model to represent the sorting process.

• Core Idea: To sort N items, an algorithm must acquire enough information to distinguish the correct sorted order from all N! possible initial permutations.
• Since each comparison is a binary choice (true/false), the height of this decision tree (representing the worst-case number of comparisons) must be large enough to accommodate N! leaves (outcomes). This leads to a height of at least \log_2(N!) , which is in \Omega(N \log N) .

Reproduce the proof that any comparison-based sort requires \Omega(N \log N) comparisons in the worst case.

Intuition: An algorithm must gather enough information to distinguish the correct sorted order from all N! possibilities. Each comparison provides one bit of information, forcing the number of steps to be at least the logarithm of the number of possibilities.

Formal Steps:

1. Model: Represent any comparison sort as a decision tree. Each internal node is a comparison (e.g., a[i] < a[j]), and each leaf is a unique permutation representing the sorted output.
2. Leaves: To be correct for any input, the tree must have at least N! leaves, one for each possible initial ordering of N distinct items.
3. Height: The worst-case number of comparisons is the length of the longest path from the root to a leaf, which is the tree's height, h.
4. Tree Property: A binary tree of height h has at most 2^h leaves.
5. Inequality: Combining these facts gives the crucial relationship: N! \le (\text{Number of Leaves}) \le 2^h .
6. Solve for h: Taking the logarithm base 2 of N! \le 2^h gives \log_2(N!) \le h .
7. Approximation: Using Stirling's approximation, we know that \log_2(N!) is in \Omega(N \log N) .
8. Conclusion: Therefore, the height h (worst-case complexity) must be in \Omega(N \log N) .

Describe the core mechanism of Selection Sort.

Selection Sort divides the array into a sorted part (left) and an unsorted part (right).

• In each main pass, it iterates through the unsorted part to find the absolute minimum element.
• It then swaps this minimum element with the element at the very beginning of the unsorted part.
• This effectively expands the sorted part by one element. The process repeats until the entire array is sorted.

Trace the execution of Selection Sort on the array [S, O, R, T]. Show the state of the array after each swap.

• Initial: [S, O, R, T]
• Pass 1: Find min in [S, O, R, T] (it's 'O'). Swap with the first element 'S'.
  • [O, S, R, T]
• Pass 2: Find min in the rest [S, R, T] (it's 'R'). Swap with the second element 'S'.
  • [O, R, S, T]
• Pass 3: Find min in the rest [S, T] (it's 'S'). Swap with the third element 'S'.
  • [O, R, S, T] (no change)
• Final: [O, R, S, T]

What are the number of comparisons and exchanges for Selection Sort on an array of size N?

• Comparisons: Always \frac{N(N-1)}{2} , which is \sim \frac{N^2}{2} .
• Exchanges: Always N (or N-1 depending on implementation).

This makes its performance insensitive to the input's initial order. It performs the same number of comparisons regardless of whether the array is sorted or not.

What is the time complexity (Best, Average, Worst) of Selection Sort?

• Best Case: \Theta(N^2)
• Average Case: \Theta(N^2)
• Worst Case: \Theta(N^2)

What is the primary advantage and disadvantage of Selection Sort?

• Advantage: Minimal data movement. It performs only \Theta(N) swaps, which is the minimum possible. This is highly valuable when write/swap operations are significantly more expensive than read/comparison operations.
• Disadvantage: The runtime is always \Theta(N^2) . It gets no performance benefit from an array that is already sorted or nearly sorted (it is not adaptive).

Describe the core mechanism of Insertion Sort.

Insertion Sort divides the array into a sorted part (left) and an unsorted part (right).

• It takes the first element from the unsorted part.
• It then compares this element with the elements in the sorted part, moving from right to left.
• It repeatedly swaps the element to the left until it finds its correct sorted position (i.e., it is no longer smaller than the item to its left).

Trace the execution of Insertion Sort on the array [S, O, R, T].

• Initial: [S, O, R, T]
• i=1 (take 'O'): Compare 'O' with 'S'. 'O' < 'S', so swap.
  • [O, S, R, T]
• i=2 (take 'R'): Compare 'R' with 'S'. 'R' < 'S' is false. Stop.
  • [O, S, R, T]
• i=3 (take 'T'): Compare 'T' with 'R'. 'T' < 'R' is false. Stop.
  • [O, S, R, T]
• Final: [O, S, R, T]

Describe the best-case scenario for Insertion Sort and its performance.

• Scenario: The array is already sorted.
• Performance:
  • Comparisons: N-1 . Each element is compared only once with the element to its left to confirm it's in place.
  • Exchanges: 0 . No swaps are needed.
  • Complexity: \Theta(N) .

Describe the worst-case scenario for Insertion Sort and its performance.

• Scenario: The array is sorted in reverse order.
• Performance:
  • Comparisons: \sim \frac{N^2}{2} . Each element must be compared against all elements in the growing sorted subarray.
  • Exchanges: \sim \frac{N^2}{2} . Each element must be swapped all the way to the beginning of the array.
  • Complexity: \Theta(N^2) .

What is the primary advantage and disadvantage of Insertion Sort?

• Advantage: It is adaptive. Its performance is extremely fast (\Theta(N)) for arrays that are already sorted or "nearly sorted". This makes it an excellent choice for small arrays or as a final-pass-improver for more complex sorts.
• Disadvantage: The average and worst-case performance is \Theta(N^2) , making it very inefficient for large, randomly ordered arrays.

Describe the core "Divide and Conquer" strategy of Merge Sort.

1. Divide: Recursively split the array in half until you have subarrays of size 1. These single-element arrays are considered sorted by definition.
2. Conquer: Repeatedly merge adjacent sorted subarrays. This merge step takes two sorted subarrays and combines them into a single, larger sorted subarray. This is repeated up the recursion chain until the entire array is one sorted unit.

The actual sorting work happens exclusively during the merge phase.

What is the time complexity and space complexity of Merge Sort?

• Time Complexity: \Theta(N \log N) for all cases (Best, Average, and Worst). Its performance is stable and not dependent on the initial order of the input.
• Space Complexity: \Theta(N) . It requires an auxiliary array of size proportional to N to perform the merge step.

What is the primary advantage and disadvantage of Merge Sort?

• Advantage: It guarantees asymptotically optimal \Theta(N \log N) performance. Its runtime is stable and predictable, regardless of the input's initial order.
• Disadvantage: It is not in-place. It requires \Theta(N) extra memory, which can be a significant drawback for very large datasets or in memory-constrained systems.

Compare Selection Sort and Insertion Sort based on data movement (exchanges). When is this difference critical?

• Selection Sort: Performs exactly \Theta(N) exchanges.
• Insertion Sort: Performs \Theta(N^2) exchanges in the average and worst cases.

Conclusion: Selection Sort is preferable when write/swap operations are significantly more expensive than read/comparison operations. For example, when sorting very large objects where moving them in memory is costly, or when writing to a medium like flash memory where write cycles are limited.

Which of these algorithms (Selection, Insertion, Merge) is "adaptive," and what does that mean?

• Insertion Sort is the only adaptive algorithm of the three.
• Adaptive means the algorithm's performance improves if the input is already partially sorted. Insertion Sort's runtime drops from \Theta(N^2) towards \Theta(N) as the input becomes more ordered.
• Selection Sort and Merge Sort are not adaptive; their runtimes are \Theta(N^2) and \Theta(N \log N) respectively, regardless of the input's initial ord