Sorting Algorithms and Trade-offs

Sorting is one of the strongest preprocessing moves in DSA. It turns unordered data into a structure where adjacency, binary search, two pointers, grouping, and range reasoning become possible. But sorting also costs time, may use memory, and may change product semantics.

What Sorting Buys

After sorting, equal or related items become neighbors. Smallest and largest values are easy to find. Two-pointer and binary-search patterns become valid. The trade-off is usually O(n log n) time for comparison sorting and potential loss of original order.

Scenario: Audit Event Ordering

A compliance dashboard sorts audit events by severity, then timestamp. If two events have equal severity, users still expect chronological order. A stable sort or explicit secondary comparator prevents confusing output.

Same Pattern in Java, Python, and JavaScript

The examples sort tickets by priority descending, then creation time ascending. The comparator encodes product semantics.

import java.util.*;

record Ticket(String id, int priority, long createdAt) {}

class TicketSort {
    static void sortTickets(List<Ticket> tickets) {
        tickets.sort(
            Comparator.comparingInt(Ticket::priority).reversed()
                .thenComparingLong(Ticket::createdAt)
        );
    }
}

When Not to Sort

• You need only the top k items and k is much smaller than n.
• The input is already indexed by a database in the needed order.
• Original order is semantically meaningful and cannot be recovered.
• The key range is tiny, making counting/bucket strategies stronger.
• The data is too large for memory and needs external sorting or streaming.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Sort tickets by priority descending, creation time ascending, then ID.
• Merge overlapping intervals.
• Arrange non-negative integers to form the largest possible concatenated number.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

record Ticket(String id, int priority, long createdAt) {}

class SortTicketsAnswer {
    static List<Ticket> sort(List<Ticket> tickets) {
        List<Ticket> copy = new ArrayList<>(tickets);
        copy.sort(Comparator.comparingInt(Ticket::priority).reversed().thenComparingLong(Ticket::createdAt).thenComparing(Ticket::id));
        return copy;
    }
}

import java.util.*;
class MergeIntervals { static int[][] merge(int[][] intervals) { Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); List<int[]> out = new ArrayList<>(); for (int[] in : intervals) { if (out.isEmpty() || out.get(out.size()-1)[1] < in[0]) out.add(in); else out.get(out.size()-1)[1] = Math.max(out.get(out.size()-1)[1], in[1]); } return out.toArray(new int[out.size()][]); } }

import java.util.*;
class LargestNumber { static String largest(int[] nums) { String[] parts = new String[nums.length]; for (int i = 0; i < nums.length; i++) parts[i] = String.valueOf(nums[i]); Arrays.sort(parts, (a, b) -> (b + a).compareTo(a + b)); if (parts[0].equals("0")) return "0"; return String.join("", parts); } }

Solved modelWorked Interview Answer

Sort tickets by priority descending, then creation time ascending. A production comparator must encode every product tie-breaker so output is deterministic and explainable.

import java.util.*;

record Ticket(String id, int priority, long createdAt) {}

class SortTicketsAnswer {
    static List<Ticket> sort(List<Ticket> tickets) {
        List<Ticket> copy = new ArrayList<>(tickets);
        copy.sort(Comparator.comparingInt(Ticket::priority).reversed().thenComparingLong(Ticket::createdAt).thenComparing(Ticket::id));
        return copy;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Sorting without stating why sorted order helps.
• Writing inconsistent comparators.
• Forgetting stability when equal keys preserve product meaning.
• Mutating input order when callers expect original order.
• Using O(n log n) sorting when top-k or bounded counting is enough.

Execution guardrailQuick-Start Checklist

• Name the sorted key.
• Define tie-breakers.
• State whether stability matters.
• Decide whether to mutate or copy input.
• State time and memory cost.
• Explain what later operation sorting enables.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice merge intervals, largest number, meeting rooms, and custom comparator problems.
• Compare TimSort, quicksort, mergesort, and heapsort conceptually.
• Review language-specific sort stability guarantees before relying on them.