Sorting Stability and When to Use Which Sort in DSA Java - Execution Trace

Concept Flow - Sorting Stability and When to Use Which Sort

Start with unsorted array

↓

Choose sorting algorithm

↓

Check stability requirement?

Yes→Use stable sort

↓

Use unstable sort

↓

Sort array accordingly

↓

Sorted array output

Flow shows choosing a sorting algorithm based on stability need, then sorting the array.

Execution Sample

DSA Java

int[] arr = {4, 2, 3, 2, 1};
// Stable sort example: Merge Sort
mergeSort(arr);
// Unstable sort example: Quick Sort
quickSort(arr);

Shows sorting an array with stable and unstable sorts to compare stability.

Execution Table

Step	Operation	Array State	Comparison	Swap?	Resulting Array
1	Start	[4, 2, 3, 2, 1]	-	-	[4, 2, 3, 2, 1]
2	Merge Sort: Divide	[4, 2, 3, 2, 1]	-	-	[4, 2, 3, 2, 1]
3	Merge Sort: Merge [4,2] and [3,2,1]	[4, 2, 3, 2, 1]	4 vs 3	Yes	[3, 4, 2, 2, 1] (partial)
4	Merge Sort: Merge [3,4] and [2,2,1]	[3, 4, 2, 2, 1]	3 vs 2	Yes	[2, 3, 4, 2, 1] (partial)
5	Merge Sort: Merge final	[2, 3, 4, 2, 1]	4 vs 2	Yes	[1, 2, 2, 3, 4] (sorted)
6	Quick Sort: Partition around pivot=1	[4, 2, 3, 2, 1]	4 vs 1	Yes	[1, 2, 3, 2, 4] (partial)
7	Quick Sort: Partition left subarray	[1, 2, 3, 2, 4]	2 vs 3	No	[1, 2, 3, 2, 4]
8	Quick Sort: Partition right subarray	[1, 2, 3, 2, 4]	3 vs 2	Yes	[1, 2, 2, 3, 4] (sorted)
9	End	[1, 2, 2, 3, 4]	-	-	[1, 2, 2, 3, 4]

💡 Sorting complete; arrays are sorted but stability differs.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	After Step 8	Final
Array	[4, 2, 3, 2, 1]	[3, 4, 2, 2, 1]	[1, 2, 2, 3, 4]	[1, 2, 3, 2, 4]	[1, 2, 2, 3, 4]	[1, 2, 2, 3, 4]
Pivot (Quick Sort)	N/A	N/A	N/A	1	3	N/A
Stable?	N/A	Yes (Merge Sort)	Yes (Merge Sort)	No (Quick Sort)	No (Quick Sort)	N/A

Key Moments - 3 Insights

Why does Merge Sort keep the order of equal elements but Quick Sort might not?

Merge Sort merges by comparing and copying elements in order, preserving original order of equals (see steps 3-5). Quick Sort swaps elements around pivots, which can reorder equal elements (see steps 6-8).

When should I choose a stable sort over an unstable sort?

Choose stable sort when the order of equal elements matters, like sorting by multiple criteria. This is shown by Merge Sort preserving order in the execution table.

Does unstable sort always produce wrong results?

No, unstable sorts still sort correctly but may reorder equal elements. This is fine if order of equals doesn't matter, as shown by Quick Sort steps.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 5 (Merge Sort final merge)?

A [1, 2, 2, 3, 4]

B [3, 4, 2, 2, 1]

C [4, 2, 3, 2, 1]

D [1, 2, 3, 2, 4]

💡 Hint

Check the 'Resulting Array' column at step 5 in the execution_table.

At which step does Quick Sort first swap elements?

A Step 8

B Step 7

C Step 6

D Step 5

💡 Hint

Look for 'Swap?' column with 'Yes' during Quick Sort steps in execution_table.

If stability was not required, which sorting algorithm from the table could be used?

A Merge Sort

B Quick Sort

C Bubble Sort

D Insertion Sort

💡 Hint

Refer to the 'Stable?' row in variable_tracker showing Quick Sort is unstable.

Concept Snapshot

Sorting Stability:
- Stable sorts keep equal elements in original order.
- Unstable sorts may reorder equal elements.
When to use:
- Use stable sort if order of equals matters (e.g., Merge Sort).
- Use unstable sort for speed if order doesn't matter (e.g., Quick Sort).

Full Transcript

This lesson shows how sorting algorithms differ in stability and when to use each. We start with an unsorted array and choose a sorting method. Merge Sort is stable, preserving the order of equal elements, shown by the array state after merges. Quick Sort is unstable and may reorder equal elements due to swaps around pivots. Stability matters when sorting by multiple criteria or when order of equal elements is important. If stability is not needed, unstable sorts like Quick Sort can be faster. The execution table traces each step, showing array states, comparisons, and swaps. Variable tracker highlights array changes and stability status. Key moments clarify why stability matters and when to choose each sort. The quiz tests understanding of array states and stability from the visuals.

Practice

1. Which sorting algorithm is stable by default, meaning it keeps the original order of equal elements?

easy

A. Heap Sort

B. Merge Sort

C. Quick Sort

D. Selection Sort

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps the relative order of equal elements unchanged after sorting.

2. Step 2: Identify stable sorting algorithms

   Merge Sort is stable because it merges sorted subarrays without changing order of equal elements. Heap Sort, Quick Sort, and Selection Sort are not stable by default.

3. Final Answer:

   Merge Sort -> Option B

4. Quick Check:

   Stable sort = Merge Sort [OK]

Hint: Stable sorts keep equal items in original order [OK]

Common Mistakes:

• Thinking Quick Sort is stable
• Confusing Heap Sort as stable
• Assuming Selection Sort preserves order

2. Which of the following is the correct Java syntax to call a stable sorting method on an array named arr?

easy

A. Collections.stableSort(arr);

B. Collections.sort(arr);

C. Arrays.stableSort(arr);

D. Arrays.sort(arr);

Solution

1. Step 1: Identify Java sorting methods

   Java's Arrays.sort() method sorts arrays and uses a stable sort for objects.

2. Step 2: Check method availability

   There is no stableSort method in Java's standard libraries. Collections.sort() works on lists, not arrays.

3. Final Answer:

   Arrays.sort(arr); -> Option D

4. Quick Check:

   Correct syntax for array sort = Arrays.sort(arr); [OK]

Hint: Use Arrays.sort for arrays, Collections.sort for lists [OK]

Common Mistakes:

• Using Collections.sort on arrays
• Assuming stableSort method exists
• Confusing array and list sorting methods

3. What is the output of the following Java code snippet?

class Item {
  int value;
  String name;
  Item(int v, String n) { value = v; name = n; }
  public String toString() { return name; }
}

Item[] arr = {
  new Item(2, "apple"),
  new Item(1, "banana"),
  new Item(2, "cherry"),
  new Item(1, "date")
};

Arrays.sort(arr, Comparator.comparingInt(i -> i.value));
for (Item i : arr) System.out.print(i + " ");

medium

A. banana date apple cherry

B. date banana cherry apple

C. apple cherry banana date

D. banana date cherry apple

Solution

1. Step 1: Understand sorting criteria and stability

   The array is sorted by value using Arrays.sort with a comparator. Java's TimSort is stable, so equal values keep original order.

2. Step 2: Trace sorting and output

   Items with value 1 are "banana" then "date" (original order). Items with value 2 are "apple" then "cherry". Sorted order: banana, date, apple, cherry.

3. Final Answer:

   banana date apple cherry -> Option A

4. Quick Check:

   Stable sort keeps equal values order: banana date apple cherry [OK]

Hint: Stable sort keeps original order for equal keys [OK]

Common Mistakes:

• Assuming unstable sort changes order of equal values
• Mixing up item names in output
• Ignoring stability of Java's Arrays.sort with comparator

4. The following code tries to sort an array of integers but does not preserve the order of equal elements. What is the main issue?

int[] arr = {4, 2, 4, 3};
Arrays.sort(arr);
// Expected stable sort but order of equal 4s changed

medium

A. Arrays.sort on primitives is not stable

B. Comparator is missing for stability

C. Array contains duplicates causing error

D. Arrays.sort cannot sort integers

Solution

1. Step 1: Check sorting method on primitive arrays

   Java's Arrays.sort on primitive types (like int[]) uses a dual-pivot quicksort which is not stable.

2. Step 2: Understand stability for primitives vs objects

   For objects, Java uses TimSort which is stable. For primitives, stability is not guaranteed, so equal elements may reorder.

3. Final Answer:

   Arrays.sort on primitives is not stable -> Option A

4. Quick Check:

   Primitive sort = unstable Arrays.sort [OK]

Hint: Primitive array sort in Java is unstable [OK]

Common Mistakes:

• Expecting stability on primitive arrays
• Thinking missing comparator causes instability
• Assuming duplicates cause errors

5. You have a list of employee records with fields id and salary. You want to sort by salary ascending but keep employees with the same salary in the order they were added. Which sorting approach is best?

hard

A. Use Heap Sort to guarantee order of equal salaries

B. Use Quick Sort for faster average performance ignoring stability

C. Use a stable sort like Merge Sort on the list by salary

D. Sort by id first, then by salary using unstable sort

Solution

1. Step 1: Understand requirement for stability

   We want to keep original order of employees with same salary, so stability is required.

2. Step 2: Choose sorting algorithm with stability

   Merge Sort is stable and sorts by salary while preserving order of equal salaries. Quick Sort and Heap Sort are not stable by default.

3. Final Answer:

   Use a stable sort like Merge Sort on the list by salary -> Option C

4. Quick Check:

   Stable sort needed for preserving order = Merge Sort [OK]

Hint: Stable sort keeps equal keys in original order [OK]

Common Mistakes:

• Choosing unstable sorts ignoring order preservation
• Sorting by id first without stable sort
• Assuming Heap Sort is stable