Sorting Stability and When to Use Which Sort in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the array is sorted in non-decreasing order after sorting.

DSA Java

for (int i = 1; i < arr.length; i++) {
    if (arr[i].key < arr[i - 1].key) {
        return [1];
    }
}

Drag options to blanks, or click blank then click option'

Atrue

B0

Cfalse

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true inside the loop instead of false.

Returning 0 or null which are not boolean values.

If any element is smaller than the previous one, the array is not sorted correctly, so return false.

2fill in blank

medium

Complete the code to perform a stable insertion sort on an array of objects with keys.

DSA Java

for (int i = 1; i < arr.length; i++) {
    Object key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j].key > key.key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + [1]] = key;
}

Drag options to blanks, or click blank then click option'

A1

B0

C-1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using j or j - 1 which places the key in the wrong position.

Using 0 or 2 which are incorrect offsets.

After shifting elements, the key should be placed at position j + 1 to maintain stability.

3fill in blank

hard

Fix the error in the merge step of merge sort to maintain stability.

DSA Java

while (i < n1 && j < n2) {
    if (L[i].key [1] R[j].key) {
        arr[k++] = L[i++];
    } else {
        arr[k++] = R[j++];
    }
}

Drag options to blanks, or click blank then click option'

A<=

B<

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using < which breaks stability by not preserving order of equal keys.

Using > or >= which reverses the order.

Using <= ensures that when keys are equal, the element from the left array is chosen first, preserving stability.

4fill in blank

hard

Complete the code to verify sorting stability using original positions (assume 'origPos' field).

DSA Java

for (int i = 1; i < arr.length; i++) {
    if (arr[i].key == arr[i-1].key && arr[i].[1] < arr[i-1].[1]) {
        return [2];
    }
}
return true;

Drag options to blanks, or click blank then click option'

AorigPos

Bfalse

Ckey

Dtrue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'key' for the position check.

Returning 'true' on violation.

For equal keys, original positions must not decrease to preserve stability; return false on violation.

5fill in blank

hard

Complete the Comparator for stable sorting by key then origPos (assume int fields).

DSA Java

Comparator<Obj> comp = Comparator.comparingInt(o -> o.[1])
    .[2](o -> o.[3]);

Drag options to blanks, or click blank then click option'

Akey

BthenComparingInt

CorigPos

DthenComparing

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping primary and secondary fields.

Using thenComparing instead of thenComparingInt for ints.

Primary sort by key, then by origPos on ties ensures stability.

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