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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Stable Sort on Objects with Equal Keys

Consider a list of objects with a key and a value. After sorting by the key using a stable sort, what is the order of the values?

DSA C#

using System;
using System.Collections.Generic;

class Item {
    public int Key { get; set; }
    public string Value { get; set; }
    public Item(int key, string value) { Key = key; Value = value; }
}

class Program {
    static void Main() {
        var items = new List<Item> {
            new Item(2, "A"),
            new Item(1, "B"),
            new Item(2, "C"),
            new Item(1, "D")
        };

        items.Sort((x, y) => x.Key.CompareTo(y.Key));

        foreach (var item in items) {
            Console.Write(item.Value + " -> ");
        }
        Console.WriteLine("null");
    }
}

A D -> B -> C -> A -> null

B B -> D -> A -> C -> null

C B -> D -> C -> A -> null

D A -> C -> B -> D -> null

💡 Hint

Remember that List.Sort in C# uses an unstable sort algorithm.

The List.Sort method in C# uses an unstable sort (QuickSort). So the relative order of equal keys is not guaranteed to be preserved. However, the code uses Sort which is unstable, so the order of items with key 1 or 2 may change. But the question asks about stable sort, so the output shown is if the sort was stable. The actual output will differ.

❓ Predict Output

intermediate

Output of Stable Sort Using LINQ OrderBy

What is the output of sorting the same list by key using LINQ's OrderBy, which is stable?

DSA C#

using System;
using System.Collections.Generic;
using System.Linq;

class Item {
    public int Key { get; set; }
    public string Value { get; set; }
    public Item(int key, string value) { Key = key; Value = value; }
}

class Program {
    static void Main() {
        var items = new List<Item> {
            new Item(2, "A"),
            new Item(1, "B"),
            new Item(2, "C"),
            new Item(1, "D")
        };

        var sorted = items.OrderBy(x => x.Key).ToList();

        foreach (var item in sorted) {
            Console.Write(item.Value + " -> ");
        }
        Console.WriteLine("null");
    }
}

A C -> A -> D -> B -> null

B A -> C -> B -> D -> null

C B -> D -> A -> C -> null

D D -> B -> C -> A -> null

💡 Hint

LINQ's OrderBy preserves the order of equal keys.

LINQ's OrderBy uses a stable sorting algorithm, so the relative order of items with equal keys is preserved. The original order of items with key 1 is B then D, and with key 2 is A then C.

🧠 Conceptual

advanced

Choosing Sorting Algorithm for Large Data with Limited Memory

You have a very large dataset that cannot fit entirely into memory. Which sorting algorithm is best suited for this scenario?

A MergeSort

B BubbleSort

C InsertionSort

D QuickSort

💡 Hint

Think about sorting that can work with data on disk and limited memory.

MergeSort can be implemented as an external sort that works well with data on disk because it processes data in chunks and merges sorted runs. QuickSort requires random access and is not suitable for external sorting. BubbleSort and InsertionSort are inefficient for large data.

🧠 Conceptual

advanced

Why Stability Matters in Sorting When Sorting by Multiple Keys

Why is it important to use a stable sort when sorting a list by multiple keys in sequence?

A Stable sort ensures the relative order of equal elements is preserved, so previous key sorting is not lost.

B Stable sort is faster than unstable sort for multiple keys.

C Stable sort uses less memory than unstable sort.

D Stable sort always sorts in ascending order.

💡 Hint

Think about sorting first by one key, then by another key without losing the first order.

When sorting by multiple keys, you sort by the least important key first, then by more important keys using a stable sort. Stability preserves the order of equal elements from previous sorts, so the final order respects all keys.

❓ Predict Output

expert

Output of Sorting Custom Objects with Unstable Sort and Equal Keys

What is the output of sorting a list of custom objects with equal keys using List.Sort (unstable) in C#?

DSA C#

using System;
using System.Collections.Generic;

class Person {
    public int Age { get; set; }
    public string Name { get; set; }
    public Person(int age, string name) { Age = age; Name = name; }
}

class Program {
    static void Main() {
        var people = new List<Person> {
            new Person(30, "Alice"),
            new Person(25, "Bob"),
            new Person(30, "Charlie"),
            new Person(25, "David")
        };

        people.Sort((p1, p2) => p1.Age.CompareTo(p2.Age));

        foreach (var p in people) {
            Console.Write(p.Name + " -> ");
        }
        Console.WriteLine("null");
    }
}

A Charlie -> Alice -> David -> Bob -> null

B David -> Bob -> Charlie -> Alice -> null

C Alice -> Charlie -> Bob -> David -> null

D Bob -> David -> Alice -> Charlie -> null

💡 Hint

List.Sort is unstable, so the relative order of equal keys may change.

List.Sort uses an unstable QuickSort, so the relative order of people with the same age is not guaranteed. However, the most common output is Bob -> David -> Alice -> Charlie -> null because the sort groups by age ascending but does not preserve original order within equal keys.

Practice

1. What does it mean when a sorting algorithm is called stable?

easy

A. It uses less memory than unstable sorts.

B. It sorts elements in ascending order only.

C. It keeps the original order of equal elements unchanged.

D. It always sorts in place without extra space.

Solution

1. Step 1: Understand stability in sorting

   A stable sort means if two elements are equal, their order stays the same as before sorting.

2. Step 2: Compare with other options

   Options B, C, and D describe other properties but not stability.

3. Final Answer:

   It keeps the original order of equal elements unchanged. -> Option C

4. Quick Check:

   Stable sort = keeps equal elements order [OK]

Hint: Stable means equal items keep their order [OK]

Common Mistakes:

• Confusing stability with sorting order
• Thinking stability means less memory use
• Assuming all sorts are stable

2. Which of the following is the correct C# syntax to call the built-in stable sort method on a list named numbers?

easy

A. Sort(numbers);

B. numbers.Sort();

C. numbers.StableSort();

D. numbers.OrderBy(x => x);

Solution

1. Step 1: Identify the correct method for sorting a List in C#

   The List<T> class has a Sort() method that sorts the list in place and is stable.

2. Step 2: Check other options

   Sort(numbers); is incorrect syntax as Sort is an instance method. numbers.OrderBy(x => x); returns an IEnumerable but does not sort the list in place. numbers.StableSort(); is not a valid method in C#.

3. Final Answer:

   numbers.Sort(); -> Option B

4. Quick Check:

   List.Sort() is correct stable sort call [OK]

Hint: Use List.Sort() to sort in place stably [OK]

Common Mistakes:

• Using LINQ OrderBy without assignment
• Assuming StableSort() exists
• Calling Sort as a standalone function

3. Consider the following C# code snippet:

var items = new List<(int id, string name)> {
  (1, "apple"),
  (2, "banana"),
  (3, "apple"),
  (4, "banana")
};
items = items.OrderBy(item => item.name).ToList();
foreach(var item in items) {
  Console.Write(item.id + " ");
}

What is the output?

medium

A. 1 3 2 4

B. 3 1 2 4

C. 2 4 1 3

D. 4 2 3 1

Solution

1. Step 1: Understand sorting by name with stability

   The list is sorted by the 'name' field. Since OrderBy is stable, equal names keep their original order.

2. Step 2: Trace the sorted order

   Names sorted alphabetically: "apple", "apple", "banana", "banana". Original order for "apple" is id 1 then 3; for "banana" is id 2 then 4.

3. Final Answer:

   1 3 2 4 -> Option A

4. Quick Check:

   Stable sort keeps equal names order: 1 3 2 4 [OK]

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

Common Mistakes:

• Assuming unstable sort changes order of equal names
• Mixing up id order after sorting
• Ignoring stability property of OrderBy

4. You wrote this code to sort a list of strings by length but it does not keep the original order of equal length strings:

var words = new List<string> { "cat", "dog", "bat", "apple" };
words.Sort((a, b) => a.Length.CompareTo(b.Length));

What is the main reason the original order of equal length strings is not preserved?

medium

A. The Sort method is unstable for custom comparers.

B. The comparison function is incorrect.

C. The list contains duplicates.

D. Strings cannot be sorted by length.

Solution

1. Step 1: Understand stability with custom comparers

   In C#, List.Sort with a custom comparer is not guaranteed to be stable, so equal keys may reorder.

2. Step 2: Check other options

   The comparison function is correct, duplicates do not affect stability, and strings can be sorted by length.

3. Final Answer:

   The Sort method is unstable for custom comparers. -> Option A

4. Quick Check:

   Custom comparer Sort is unstable [OK]

Hint: Custom comparer Sort may be unstable [OK]

Common Mistakes:

• Blaming comparison function for instability
• Thinking duplicates cause instability
• Assuming all Sort calls are stable

5. You have a list of employee records with id and department. You want to sort employees by department alphabetically but keep the original order of employees within the same department. Which sorting approach is best?

hard

A. Use an unstable sort by department for faster sorting.

B. Sort by department descending to keep order.

C. Sort by id first, then sort by department using unstable sort.

D. Use a stable sort by department to keep original order within groups.

Solution

1. Step 1: Identify requirement to keep original order within same department

   This means sorting must be stable so equal departments keep their original order.

2. Step 2: Evaluate options

   Using an unstable sort by department loses original order within groups. Using a stable sort by department preserves it. Sorting by id first then by department with an unstable sort does not guarantee preservation. Sorting descending does not address stability.

3. Final Answer:

   Use a stable sort by department to keep original order within groups. -> Option D

4. Quick Check:

   Stable sort keeps order within equal keys [OK]

Hint: Stable sort preserves order within equal keys [OK]

Common Mistakes:

• Using unstable sort and losing order
• Sorting by id after department breaks order
• Sorting descending does not preserve order