Sorting Stability and When to Use Which Sort in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Stable vs Unstable Sort on Objects

Consider sorting a list of objects by their integer key. Which output shows the list after a stable sort by key?

DSA Java

class Item {
  int key;
  String name;
  Item(int key, String name) { this.key = key; this.name = name; }
  public String toString() { return key + ":" + name; }
}

List<Item> items = new ArrayList<>();
items.add(new Item(2, "A"));
items.add(new Item(1, "B"));
items.add(new Item(2, "C"));
items.add(new Item(1, "D"));

// After stable sort by key ascending
items.sort(Comparator.comparingInt(i -> i.key));
System.out.println(items.stream().map(Item::toString).collect(Collectors.joining(", ")));

A 1:B, 1:D, 2:A, 2:C

B 1:D, 1:B, 2:C, 2:A

C 1:B, 2:A, 1:D, 2:C

D 2:A, 2:C, 1:B, 1:D

💡 Hint

Stable sort keeps the original order of equal keys.

Stable sorting keeps the relative order of items with equal keys. Here, items with key 1 appear in original order B then D, and key 2 items appear as A then C.

🧠 Conceptual

intermediate

When to Prefer Stable Sorts?

Which situation best explains when you should use a stable sorting algorithm?

A When you want to maintain the order of equal elements after sorting by one key before sorting by another key

B When you want the fastest possible sorting regardless of element order

C When the data set is very small and stability does not matter

D When you want to sort elements in descending order only

💡 Hint

Think about sorting by multiple keys step-by-step.

Stable sorts keep the order of equal elements, which is important when sorting by multiple keys in sequence to preserve previous orderings.

❓ Predict Output

advanced

Output of Unstable Sort on Duplicate Keys

What is the output of this code using an unstable sort on the same list of items?

DSA Java

class Item {
  int key;
  String name;
  Item(int key, String name) { this.key = key; this.name = name; }
  public String toString() { return key + ":" + name; }
}

List<Item> items = new ArrayList<>();
items.add(new Item(2, "A"));
items.add(new Item(1, "B"));
items.add(new Item(2, "C"));
items.add(new Item(1, "D"));

// Using Collections.sort with a custom comparator (unstable in some implementations)
Collections.sort(items, (i1, i2) -> Integer.compare(i1.key, i2.key));
System.out.println(items.stream().map(Item::toString).collect(Collectors.joining(", ")));

A 1:B, 2:A, 1:D, 2:C

B 1:B, 1:D, 2:A, 2:C

C 1:D, 1:B, 2:C, 2:A

D 2:A, 2:C, 1:B, 1:D

💡 Hint

Unstable sort may reorder equal keys arbitrarily.

Unstable sorts do not guarantee the order of equal keys, so the relative order of items with key 1 and key 2 may change.

🧠 Conceptual

advanced

Choosing Sorting Algorithm Based on Data and Stability

You have a large dataset with many duplicate keys and need to sort it by one key while preserving the order of duplicates. Which sorting algorithm is best?

A Quick Sort, because it is the fastest on average even if unstable

B Merge Sort, because it is stable and efficient for large data

C Heap Sort, because it uses less memory than Merge Sort

D Selection Sort, because it is simple and stable

💡 Hint

Consider stability and efficiency for large data.

Merge Sort is stable and has O(n log n) time, making it suitable for large data with duplicates where stability matters.

🔧 Debug

expert

Identify the Stability Issue in Custom Sort Implementation

Given this custom sort code, what causes it to be unstable?

DSA Java

class Item {
  int key;
  String name;
  Item(int key, String name) { this.key = key; this.name = name; }
}

List<Item> items = new ArrayList<>();
items.add(new Item(1, "X"));
items.add(new Item(1, "Y"));
items.add(new Item(2, "Z"));

items.sort((a, b) -> a.key - b.key);

// What causes instability here?

A The comparator does not compare the name field to break ties

B Not using a stable sort method like Collections.sort causes instability

C The list contains duplicate keys which always cause instability

D Using subtraction (a.key - b.key) in comparator can cause integer overflow and unstable ordering

💡 Hint

Think about how comparator subtraction can affect order and stability.

Using subtraction in comparator can cause overflow and does not guarantee consistent ordering, leading to instability. Proper comparator should use Integer.compare.

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