Sorting Stability and When to Use Which Sort in DSA Java - Time & Space Complexity

Time Complexity: Sorting Stability and When to Use Which Sort

O(n²)

Understanding Time Complexity

Sorting algorithms differ in how fast they run and whether they keep equal items in the same order.

We want to understand how their speed changes with input size and when to pick each sort.

Scenario Under Consideration

Analyze the time complexity of this simple insertion sort code.

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

This code sorts an array by inserting each element into its correct place among the sorted elements before it.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: The inner while loop moves elements to make space for the key.
• How many times: The outer for loop runs once per element, and the inner loop can run up to i times.

How Execution Grows With Input

As the array grows, the number of moves grows faster because each new element may need to shift many others.

Input Size (n)	Approx. Operations
10	About 50 moves
100	About 5,000 moves
1000	About 500,000 moves

Pattern observation: The work grows roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the input size, the work roughly quadruples, making it slower for big lists.

Common Mistake

[X] Wrong: "All sorting algorithms run equally fast regardless of input size."

[OK] Correct: Some sorts like insertion sort slow down a lot as input grows, while others like merge sort handle large inputs more efficiently.

Interview Connect

Knowing when a sort is stable and how fast it runs helps you choose the right tool in coding challenges and real projects.

Self-Check

What if we used merge sort instead of insertion sort? How would the time complexity change?

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