Searching, Sorting, and Selection

Introduction

Searching and sorting are among the most frequently used operations in software systems. A search locates an item satisfying a condition; sorting arranges items according to an ordering rule; selection identifies an item with a particular rank, such as the smallest, largest, or median value. These operations support databases, compilers, operating systems, scientific applications, e-commerce platforms, and data-analysis software.

The choice of algorithm depends on more than asymptotic time complexity. A professional implementation must also consider whether the data is already ordered, whether duplicate values occur, whether equal elements must retain their original order, how much additional memory is available, and whether a trusted library implementation is preferable to custom code.

Learning Objectives

By the end of this chapter, you should be able to:

• implement linear and binary search in Java and Python;
• explain the assumptions and invariants of common searching algorithms;
• compare insertion, merge, quick, heap, counting, and radix sort;
• distinguish stable, unstable, in-place, adaptive, comparison-based, and non-comparison-based algorithms;
• analyze best-case, average-case, and worst-case time complexity;
• use selection algorithms to find order statistics;
• select suitable library routines and evaluate their limitations.

1. Ordering, Keys, and Comparisons

An algorithm sorts records by a key. For example, a student record may contain a name, identification number, and grade; the grade can be the sorting key. An ordering should normally be total, meaning that any two comparable values can be placed in a consistent order. In practice, a comparator defines whether one key is less than, equal to, or greater than another.

A sorting algorithm is stable if equal-key records preserve their original relative order. Stability matters when data is sorted in stages. For example, if employee records are first sorted by department and then stably sorted by salary, employees with equal salary remain ordered by department.

An algorithm is in-place when it uses only a small amount of extra storage, usually O(1) auxiliary space, apart from the input array. The phrase is sometimes used less strictly, so documentation should state the exact memory requirement. An algorithm can be in-place but unstable, or stable but not in-place.

Comparison-based algorithms obtain ordering information only through comparisons. Their general worst-case lower bound is:

for sorting an arbitrary collection of n distinct elements by comparisons. This lower bound does not apply to counting and radix sort because those algorithms exploit properties of the keys rather than relying solely on pairwise comparisons.

2. Linear Search

Linear search examines elements sequentially until it finds the target or reaches the end. It requires no ordering assumption and works with arrays, lists, and streams.

Pseudocode

linearSearch(A, target)
    for i from 0 to length(A) − 1
        if A[i] equals target
            return i
    return −1

The returned index is the first matching position. If the target is absent, −1 is returned. For an array of n elements, the best case requires one comparison, while the worst case requires n comparisons. If every position is equally likely and the target is present, the average is approximately (n + 1) / 2 comparisons. These statements assume constant-time element access and equality testing.

Java and Python implementations

static int linearSearch(int[] a, int target) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == target) return i;
    }
    return -1;
}

def linear_search(values, target):
    for i, value in enumerate(values):
        if value == target:
            return i
    return -1

Linear search is appropriate for small or unsorted collections, linked lists, and situations in which only one search is required. Its principal limitation is that repeated searches over a large collection may become expensive.

3. Binary Search

Binary search is substantially faster, but it requires the input to be sorted according to the same ordering used by the search. It repeatedly compares the target with the middle element and discards the half that cannot contain the target.

For inclusive bounds low and high, a safe midpoint is:

This form avoids integer overflow in fixed-width languages when low and high are large. Each iteration maintains the invariant that, if the target occurs, it lies within the current interval.

static int binarySearch(int[] a, int target) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

The search interval is approximately halved at each iteration. Therefore the time complexity is O(log n) in the worst and average cases, and O(1) in the best case. Iterative binary search uses O(1) auxiliary space. A recursive version uses O(log n) call-stack space.

When duplicates exist, ordinary binary search may return any matching index. Two useful variants are lower bound, the first position whose value is greater than or equal to the target, and upper bound, the first position whose value is greater than the target. These variants are useful for counting occurrences: the number of target values is upper bound minus lower bound.

Binary search is unsuitable for an unsorted array and is often inefficient on a linked list because locating the middle element is not constant time. It is also important to distinguish sorting cost from searching cost: sorting once may be worthwhile if many searches follow, but not necessarily for a single query.

4. Insertion Sort

Insertion sort builds a sorted prefix. At each step it removes the next item and shifts larger elements to the right until the correct position is available.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Insertion sort is stable and in-place. Its best-case time is O(n) when the input is already sorted. Average and worst-case time are O(n²), with worst-case behavior occurring for reverse-sorted input. It is adaptive: performance improves as the input becomes closer to sorted. It is often effective for small arrays and is commonly used inside sophisticated hybrid sorting algorithms for small subarrays.

5. Merge Sort

Merge sort divides the collection into two halves, recursively sorts each half, and merges the sorted halves. During merging, the smallest remaining front element is copied into an output sequence.

The recurrence for a standard balanced merge sort is:

The two recursive calls account for the first term and the linear merge accounts for the second. Consequently, the best, average, and worst-case time complexities are all Θ(n log n). A conventional array implementation requires O(n) auxiliary space. Merge sort is stable when the merge operation chooses the left item first when keys are equal.

Merge sort is attractive when predictable performance and stability are important. It is also well suited to external sorting because files can be divided into sorted runs and merged sequentially. Its additional memory and data movement may make it less attractive for a small, memory-constrained in-memory array.

6. Quicksort

Quicksort selects a pivot, partitions the array into elements less than, equal to, and greater than the pivot, and recursively sorts the partitions. The partition strategy and pivot choice strongly influence performance.

If partitions are balanced, the recurrence is approximately:

and the time is Θ(n log n). If one partition contains nearly all elements, the recurrence becomes approximately T(n) = T(n − 1) + Θ(n), producing Θ(n²) worst-case time. Randomized pivots, median-of-three selection, and three-way partitioning reduce the likelihood or impact of poor partitions, but do not change the formal worst-case bound unless the implementation includes additional safeguards.

Quicksort is often in-place and has good cache locality. Basic two-way quicksort is not stable. Three-way partitioning is especially useful when many duplicate keys occur because it groups values equal to the pivot and avoids repeatedly processing them.

7. Heap Sort

A binary heap is a complete binary tree represented efficiently in an array. In a max-heap, every parent is greater than or equal to its children. Repeatedly removing the maximum and placing it at the end produces ascending order.

Building a heap from an arbitrary array using bottom-up heap construction takes O(n), not O(n log n). Each extraction takes O(log n), and there are n extractions, so heap sort takes O(n log n) time in the best, average, and worst cases. It is in-place but unstable.

Heap sort offers a strong worst-case guarantee with low auxiliary memory. However, it often has poorer cache behavior than quicksort and may be slower in practice when average performance is the main concern.

8. Counting and Radix Sort

Counting sort

Counting sort is suitable when keys are integers in a manageable range. For keys from 0 through k − 1, it counts occurrences and reconstructs the result. A stable version uses cumulative counts to place records in output order.

Its time complexity is:

where n is the number of records and k is the number of possible key values. Its auxiliary space is typically O(n + k) for a stable implementation. Counting sort is not comparison-based. It becomes impractical when k is very large relative to n, such as sorting a few values drawn from a huge integer range.

Radix sort

Radix sort processes keys digit by digit, using a stable sorting method at each position. In least-significant-digit radix sort, the least significant digit is processed first and the most significant digit last. Stability at every pass is essential.

For d digits and digit range b, the common complexity is:

This assumes fixed-width keys and a stable linear-time pass, such as counting sort. Radix sort can outperform comparison sorts for fixed-format integers, identifiers, or strings, but it requires key representation and digit processing to be defined carefully. Signed integers, variable-length strings, and locale-sensitive text require additional design decisions.

9. Selection and Order Statistics

The kth order statistic is the item that would occupy position k after sorting, using a stated convention. Thus the minimum is the first order statistic and the maximum is the last. The median is the middle item; for an even number of values, a convention is needed, often the mean of the two central values for numerical data.

Sorting followed by indexing solves selection in O(n log n). However, quickselect partitions around a pivot and recursively processes only the side containing the desired rank. Its average time is O(n), but its worst-case time is O(n²) with consistently poor pivots. Randomized pivot selection is common.

The deterministic median-of-medians method guarantees linear worst-case time, O(n), but has larger constants and is less common in ordinary application code. Selection algorithms are useful for percentiles, top-k reporting, robust statistics, and finding thresholds without fully sorting the data.

10. Comparative Evaluation

Complexity describes growth as input size changes; it does not measure every practical cost. Constant factors, memory locality, allocation, comparator cost, and input distribution can determine which algorithm is fastest in a real system.

11. Library Implementations in Java and Python

Library sorting functions should normally be preferred in production because they are tested, optimized, and maintained. Java provides Arrays.sort for arrays and Collections.sort or List.sort for lists. Java object sorting is stable in modern standard-library implementations, while primitive-array sorting may use a different algorithm and does not provide record stability in the same sense. Developers should consult the version-specific API documentation rather than assume identical behavior for all overloads.

Python's list.sort() and sorted() use Timsort, a stable adaptive algorithm that exploits existing ordered runs. list.sort() modifies the list and returns None; sorted() creates and returns a new list. Both accept a key function, which is generally preferable to repeatedly computing complex comparisons.

Example:

records.sort(key=lambda r: r["department"])
records.sort(key=lambda r: r["salary"], reverse=True)

Because Python sorting is stable, the second sort preserves department order among employees with equal salary. In Java, use a comparator and compose it explicitly when a multi-key ordering is required.

Library search functions also deserve attention. Python's bisect module supports binary-search insertion points in sorted lists, but insertion into a Python list remains O(n) because elements must be shifted. Java's Arrays.binarySearch requires a sorted array and returns a specified index if duplicates exist; the exact duplicate selected should not be treated as a stable first or last occurrence unless the program implements that requirement.

12. Applied Case: Ranking Examination Results

Background

A training institution stores 500,000 examination records. Each record contains a candidate identifier, course, score, and submission time. Administrators need a full ranking by score, while an analytics service repeatedly requests the median score and the top 100 candidates.

Problem

A naive design sorts the entire data set for every request. This wastes time when only a percentile or small top-k set is required. It also needs a clear policy for ties: candidates with equal scores should be ordered by submission time and then identifier.

Analysis and approach

For the official ranking, a stable library sort with a composite key is appropriate. The key is score descending, submission time ascending, and identifier ascending. A stable sort makes the treatment of equal composite keys predictable.

For the median, quickselect can reduce expected work from O(n log n) to O(n), although the implementation should use a robust pivot strategy and be tested against adversarial input. For the top 100 candidates, maintaining a min-heap of size 100 requires O(n log 100), effectively linear in the number of records because 100 is fixed. The heap contains the current best 100 records; a new record replaces the smallest member when it is better.

Scores lie between 0 and 100, so counting sort could be used for score-only grouping in O(n + 101). It cannot by itself resolve all tie-breaking fields unless the implementation stores records in stable input order and performs additional ordering. Thus the key range makes counting attractive for some reports, but not automatically for the complete ranking.

Outcome

The system uses a library sort for the official complete ranking, heap-based top-k processing for dashboard requests, and selection for percentile queries. It documents tie rules, tests duplicate-heavy data, and avoids assuming that a binary search result identifies the first duplicate.

Learning points

• Algorithm selection must follow the query, not merely the data type.
• Stability is a business requirement when tie order matters.
• A restricted key range may enable non-comparison sorting.
• Library algorithms reduce implementation risk, but their contracts must be read carefully.

13. Testing, Limitations, and Professional Practice

Search and sort implementations should be tested with empty arrays, one-element arrays, duplicate values, already sorted data, reverse-sorted data, negative values, extreme numeric values, and records with equal keys. Property-based tests can verify that the output is ordered and is a permutation of the input. For binary search, tests should verify the sorted-input precondition and boundary positions.

Common defects include an incorrect loop boundary, failure to update a binary-search bound, integer overflow in midpoint calculation, unstable tie handling, misuse of a comparator that violates transitivity, and excessive memory use in merge or counting sort. A comparator should define a consistent ordering; contradictory results can cause library algorithms to behave unpredictably.

Security and governance issues also arise. Sorting personal records may expose sensitive data through logs or temporary files. External sorting should protect intermediate files, and ranking systems should document tie-breaking rules to support fairness and auditability. Algorithmic efficiency can affect access to services when users with larger data sets experience delays, so performance testing should include realistic and worst-case inputs.

Artificial intelligence does not replace these fundamentals. AI-assisted code generation may produce a plausible but incorrect binary search or an unstable sorting pipeline. Generated code must be reviewed for preconditions, complexity, memory use, duplicate handling, and library contracts. Benchmarking should use representative data rather than a single favorable example.

Chapter Summary

Searching locates data, sorting establishes order, and selection retrieves a rank without necessarily ordering the entire collection. Linear search requires no ordering and has worst-case O(n) time. Binary search requires sorted data and has O(log n) time with random access.

Insertion sort is stable, in-place, adaptive, and useful for small or nearly sorted inputs. Merge sort provides stable O(n log n) performance but normally needs linear auxiliary storage. Quicksort is often fast and cache-friendly, but pivot choice can produce quadratic worst-case behavior and it is normally unstable. Heap sort provides in-place O(n log n) worst-case performance but is unstable. Counting and radix sort can beat comparison-based bounds when key structure is suitable.

Selection algorithms, including quickselect, are valuable for medians, percentiles, and top-k tasks. In professional systems, library implementations are usually the safest choice, provided their ordering, stability, mutability, and precondition contracts are understood.

Key Terms

Linear search: Sequentially examines elements until a target is found or the collection ends.

Binary search: Searches a sorted, randomly accessible collection by repeatedly halving the search interval.

Comparator: A rule that determines the relative order of two values or records.

Key: The field or derived value used for ordering or searching.

Stable sort: A sort that preserves the relative order of equal-key records.

In-place algorithm: An algorithm using limited auxiliary storage while modifying the input structure.

Adaptive algorithm: An algorithm whose performance improves when input has useful existing structure.

Comparison sort: A sort that obtains ordering information through comparisons.

Counting sort: A non-comparison sort based on frequencies of integer keys.

Radix sort: A digit-by-digit or character-by-character non-comparison sort.

Pivot: The element or value used to partition data in quicksort or quickselect.

Partition: The rearrangement of elements around a selected pivot or boundary.

Heap: A complete-tree structure satisfying a parent-child priority property.

Order statistic: The element occupying a specified rank in sorted order.

Quickselect: A partition-based algorithm for selecting one order statistic.

Lower bound: The first position whose value is at least a target value.

Upper bound: The first position whose value is greater than a target value.

Timsort: A stable adaptive sorting algorithm used by Python's standard list sorting.

Review Questions

Short Answer Questions

1. Why does binary search require sorted data?
2. Define stability in the context of sorting.
3. State the worst-case time complexity of insertion sort.
4. Why can counting sort outperform comparison sorts?
5. What is the purpose of a pivot in quicksort?

Long Answer Questions

1. Explain linear and binary search, including their assumptions, invariants, and complexities.
2. Compare merge sort, quicksort, and heap sort with respect to time, space, stability, and practical use.
3. Explain counting sort and radix sort, including the conditions under which each is appropriate.
4. Describe how library sorting functions in Java and Python differ in mutability and key handling.
5. Explain why selection may be preferable to sorting when only a median or percentile is required.

Analytical / Application Questions

1. A collection contains one million records and is already almost sorted. Which sorting approach would you investigate first, and why?
2. A system must return the top 50 scores from ten million values but does not need a complete ranking. Design an algorithm and justify its complexity.
3. A binary search sometimes fails only when the target is near an array boundary. Identify likely implementation errors and propose test cases.

Multiple Choice Questions with Answers

Question 1

What is the worst-case time complexity of binary search on a sorted array?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: B. O(log n)

Question 2

Which property guarantees that equal-key records retain their original relative order?

A. In-place behavior

B. Adaptiveness

C. Stability

D. Partitioning

Correct Answer: C. Stability

Question 3

Which algorithm is usually most suitable for a small, nearly sorted array?

A. Insertion sort

B. Heap sort

C. Counting sort with a huge key range

D. Radix sort for variable-format records

Correct Answer: A. Insertion sort

Question 4

What is the worst-case time complexity of standard quicksort with consistently poor partitions?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n²)

Correct Answer: D. O(n²)

Question 5

Which sorting algorithm normally requires linear auxiliary space and can be stable?

A. Merge sort

B. Heap sort

C. Basic in-place quicksort

D. Selection by repeated maximum extraction

Correct Answer: A. Merge sort

Question 6

Counting sort is most appropriate when:

A. The input is a linked list of arbitrary objects

B. The integer key range is manageable

C. Only comparisons are permitted

D. The data has no repeat values

Correct Answer: B. The integer key range is manageable

Question 7

What is the average time complexity of randomized quickselect?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 8

What does Python's list.sort() do?

A. Returns a newly sorted list and leaves the original unchanged

B. Sorts the list in place and returns None

C. Requires the list to be sorted already

D. Performs only binary search

Correct Answer: B. Sorts the list in place and returns None

Question 9

Why is a stable pass essential in least-significant-digit radix sort?

A. It preserves the ordering established by less significant digits

B. It reduces every pass to constant time

C. It eliminates the need to inspect digits

D. It guarantees comparison-based sorting

Correct Answer: A. It preserves the ordering established by less significant digits

Question 10

For a top-100 query over a very large stream, which structure is especially suitable?

A. A min-heap of size 100

B. A binary-search tree containing every possible integer

C. An array sorted after every insertion

D. A linear search restarted for every record

Correct Answer: A. A min-heap of size 100