Sorting Stability and When to Use Which Sort in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for a sorting algorithm to be stable?

A stable sorting algorithm keeps the original order of equal elements the same after sorting. For example, if two items have the same value, they stay in the order they appeared before sorting.

beginner

Name a common stable sorting algorithm.

Merge Sort is a common stable sorting algorithm. It keeps equal elements in their original order while sorting.

intermediate

Why might you choose an unstable sort like Quick Sort over a stable sort?

Quick Sort is often faster and uses less memory than stable sorts. If you don't need to keep the order of equal elements, Quick Sort is a good choice for speed.

intermediate

When is it important to use a stable sorting algorithm?

Use a stable sort when you want to sort by multiple criteria step-by-step. For example, first sort by age, then by name. Stability keeps the previous order intact.

intermediate

What is a key difference between Merge Sort and Heap Sort regarding stability?

Merge Sort is stable, meaning it keeps equal elements in order. Heap Sort is unstable, so equal elements might change order after sorting.

Which sorting algorithm is stable by default?

A Merge Sort

B Quick Sort

C Heap Sort

D Selection Sort

Merge Sort keeps the order of equal elements, so it is stable. Quick Sort, Heap Sort, and Selection Sort are generally unstable.

Why choose a stable sort when sorting by multiple keys?

A To keep the order of equal elements from previous sorts

B Because stable sorts are always faster

C To use less memory

D Because unstable sorts can't sort multiple keys

Stable sorts keep the order of equal elements, which helps when sorting by multiple keys step-by-step.

Which sorting algorithm is usually fastest but unstable?

A Bubble Sort

B Quick Sort

C Insertion Sort

D Merge Sort

Quick Sort is often the fastest in practice but is unstable.

If you want to sort a large list with limited memory and don't care about stability, which sort is best?

A Counting Sort

B Merge Sort

C Bubble Sort

D Quick Sort

Quick Sort uses less memory than Merge Sort and is fast, making it good for large lists when stability is not needed.

Which sorting algorithm is stable and good for linked lists?

A Heap Sort

B Quick Sort

C Merge Sort

D Selection Sort

Merge Sort is stable and works well with linked lists because it doesn't require random access.

Explain what sorting stability means and why it matters when sorting by multiple criteria.

Think about how sorting twice by different keys keeps the order.

Describe when you would choose Quick Sort over Merge Sort and the trade-offs involved.

Consider performance and stability needs.