Sorting and Searching Algorithms Questions

Comparison and non-comparison sorting (quicksort with its pivot and partition choices and hybrid cutoffs, mergesort, heapsort as a sort, insertion/selection/bubble, counting/radix/bucket), their stability, in-place behavior, stack depth and lower bounds, and choosing a sort from input constraints, including near-sorted data, library sorts (Timsort, introsort, language defaults), comparator design and expensive comparisons or copies. Also selection (quickselect, median-of-medians, nth_element), external merge sorting of data larger than memory (run generation and merge passes), and binary search with its variants: first/last occurrence, lower/upper bound, rotated arrays with or without duplicates, peak and mountain arrays, sorted matrices, unbounded search, loop-invariant correctness and off-by-one pitfalls, and binary search on an answer space (discrete or continuous, including k-th smallest by value). Includes divide-and-conquer reasoning for sorts (merge step, merging sorted arrays, median of two sorted arrays, inversion counting). Excludes heap data-structure mechanics and heap-based top-k and k-way merging, trees and tries, general graph search, distributed data-processing systems, approximate nearest-neighbor and streaming-sketch algorithms, and abstract Big-O comparison.

MediumTechnical
49 practiced

Explain Introsort (introspective sort): how it combines quicksort, heapsort fallback, and insertion sort for small partitions. Provide pseudocode for introsort and explain why it guarantees O(n log n) worst-case behavior. Describe how std::sort implements these ideas and discuss tuning parameters like recursion-depth threshold.

HardTechnical
63 practiced

You are given a comparator supplied by a user that may be inconsistent (non-transitive or throwing exceptions). How would you design a robust sort routine to detect comparator issues, ensure determinism where possible, and fail gracefully? Discuss production safeguards and corrective strategies.

MediumTechnical
56 practiced

Explain the behavior and guarantees of C++ STL's nth_element algorithm. What ordering properties does it provide for elements, what is its typical complexity, and when is nth_element preferable to fully sorting the container in practice?

EasyTechnical
95 practiced

Implement lower_bound and upper_bound on a sorted array: the first index with value >= target and the first index with value > target. Use them to count occurrences, and list the off-by-one pitfalls you checked.

MediumTechnical
65 practiced

You need the top 100 values out of 10 million numbers. Compare sorting then slicing, quickselect, a size-k heap, and the library's nth_element, and recommend one with complexity and memory reasoning.

That is every published Sorting and Searching Algorithms question for Game Developer so far. Browse the other topics in this category, or practice this one interactively.