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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this stable sort on a list of structs?

Given a list of structs with fields value and id, a stable sort is applied by value. What is the order of id after sorting?

DSA Go

package main

import (
	"fmt"
	"sort"
)

type item struct {
	value int
	id    int
}

func main() {
	items := []item{{3, 1}, {1, 2}, {3, 3}, {2, 4}}
	sort.SliceStable(items, func(i, j int) bool {
		return items[i].value < items[j].value
	})
	for _, it := range items {
		fmt.Print(it.id, " ")
	}
}

A 2 4 3 1

B 1 3 4 2

C 4 2 1 3

D 2 4 1 3

💡 Hint

Stable sort keeps the original order of equal elements.

The stable sort orders by value: 1, 2, 3, 3. For equal values (3 and 3), the original order of id 1 then 3 is preserved.

🧠 Conceptual

intermediate

Which sorting algorithm is stable by default?

Choose the sorting algorithm that is stable by default without extra modifications.

A Merge Sort

B Selection Sort

C Heap Sort

D Quick Sort

💡 Hint

Think about which algorithm merges sorted lists preserving order.

Merge Sort is stable because it merges two sorted halves by comparing elements and preserving their original order when equal.

🚀 Application

advanced

When should you prefer an unstable sort over a stable sort?

Choose the best scenario to prefer an unstable sort algorithm.

A When memory usage must be minimal and speed is critical

B When sorting linked lists where stability is guaranteed

C When you need to preserve the relative order of equal elements

D When sorting small arrays where stability is required

💡 Hint

Unstable sorts often use less memory and can be faster.

Unstable sorts like Quick Sort or Heap Sort often use less memory and can be faster, so prefer them when stability is not needed but speed and memory are important.

🔧 Debug

advanced

What error occurs in this Go code using sort.Slice instead of sort.SliceStable?

What is the output or error of this code that sorts a slice of structs by value but uses sort.Slice instead of sort.SliceStable?

DSA Go

package main

import (
	"fmt"
	"sort"
)

type item struct {
	value int
	id    int
}

func main() {
	items := []item{{3, 1}, {1, 2}, {3, 3}, {2, 4}}
	sort.Slice(items, func(i, j int) bool {
		return items[i].value < items[j].value
	})
	for _, it := range items {
		fmt.Print(it.id, " ")
	}
}

A 2 4 1 3

B 2 4 3 1

C Compilation error

D Runtime panic

💡 Hint

sort.Slice is not stable, so equal elements may reorder.

sort.Slice sorts but is not stable, so the two items with value 3 may swap order. The output is 2 4 3 1 instead of 2 4 1 3.

🧠 Conceptual

expert

Why is stability important in multi-level sorting?

Choose the best explanation why stable sorting is crucial when sorting by multiple keys in sequence.

A It guarantees the fastest sorting time for large datasets

B It reduces the total number of comparisons needed

C It preserves the order of previous sorts when sorting by the next key

D It allows sorting in place without extra memory

💡 Hint

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

Stable sorting preserves the order of equal elements, so when sorting by multiple keys, the previous key's order is kept intact after sorting by the next key.