Searching, Sorting, and Selection

Introduction

Searching and sorting are among the most frequently performed operations in computing. A database index searches for records, a compiler sorts symbols or tokens, a web application ranks results, and an operating system selects tasks according to priority. Although these operations may appear simple, their design involves important questions about time complexity, memory use, data organization, stability, and worst-case behavior.

Searching locates an item satisfying a key or condition. Sorting rearranges items into a specified order. Selection identifies an item with a particular rank, such as the smallest element, the median, or the kth smallest element. These problems are closely related: sorting can make repeated searching efficient, while selection can sometimes be performed without fully sorting the data.

This chapter develops linear and binary search; major comparison-based algorithms; non-comparison sorting; stability and in-place operation; lower bounds; partitioning; and order statistics. The emphasis is on both implementation and informed algorithm selection.

Learning Objectives

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

1. Compare linear search and binary search and identify their preconditions.
2. Explain and implement insertion sort, selection sort, bubble sort, merge sort, quicksort, and heap sort.
3. Distinguish stable, unstable, in-place, and out-of-place algorithms.
4. Explain the comparison-sorting lower bound.
5. Use counting sort, radix sort, and bucket sort under appropriate assumptions.
6. Apply partitioning to selection and quicksort.
7. Analyze order statistics and choose suitable algorithms for practical problems.

1. Searching

1.1 Linear Search

Linear search examines items sequentially until it finds the target or reaches the end. It requires no ordering of the data and works with arrays, linked lists, streams, and other sequential structures.

linearSearch(A, target)
    for i ← 0 to length(A) − 1
        if A[i] = target
            return i
    return NOT_FOUND

If the target is equally likely to be at any of n positions, a successful search examines approximately (n + 1) ÷ 2 elements on average. An unsuccessful search examines n elements. Thus the worst-case time complexity is O(n), the best case is O(1), and the auxiliary space complexity is O(1).

Linear search is often preferable when the collection is small, unsorted, frequently changing, or stored in a linked structure. It is also appropriate when only one search is required and the cost of sorting would not be justified.

1.2 Binary Search

Binary search requires a sorted random-access sequence. It compares the target with the middle element and eliminates the half that cannot contain the target.

binarySearch(A, target)
    low ← 0
    high ← length(A) − 1
    while low ≤ high
        mid ← low + floor((high − low) / 2)
        if A[mid] = target
            return mid
        else if A[mid] < target
            low ← mid + 1
        else
            high ← mid − 1
    return NOT_FOUND

The expression for mid avoids the possible integer overflow of (low + high) ÷ 2 when indices are very large. After each unsuccessful comparison, the remaining search interval is approximately halved. The number of comparisons is O(log₂ n), with O(1) auxiliary space for the iterative version.

Binary search is not automatically suitable for linked lists. Finding the middle of a linked list requires traversal, so repeatedly locating middle elements can destroy the expected logarithmic performance. Binary search is especially valuable when a sorted collection is searched many times.

1.3 Variants and Correctness Conditions

Practical binary-search libraries commonly provide variants:

• First occurrence: returns the smallest index containing the target.
• Last occurrence: returns the largest index containing the target.
• Lower bound: returns the first index whose value is greater than or equal to the target.
• Upper bound: returns the first index whose value is strictly greater than the target.

A reliable implementation maintains a loop invariant: if the target exists, it remains within the current search interval. Boundary errors commonly arise from inconsistent choices such as inclusive versus exclusive upper bounds. Testing should include an empty array, a one-element array, duplicate values, a target smaller than every element, and a target larger than every element.

1.4 Choosing a Search Method

2. Foundations of Sorting

A sorting algorithm rearranges records according to a key and an ordering relation, usually ascending or descending order. A correct sorting algorithm must produce a sequence in which each adjacent pair is ordered according to the chosen relation and must preserve every input record, including duplicates.

Stability

A sorting algorithm is stable if records with equal keys retain their original relative order. Stability matters when records contain multiple fields. For example, if employees are first sorted by department and then stably sorted by salary, employees with equal salaries remain ordered by department.

In-Place Operation

An algorithm is commonly called in-place when it uses O(1) or otherwise small auxiliary memory beyond the input array. The term has variations in the literature, so the exact memory convention should be stated. In-place does not mean that the algorithm uses no memory at all; recursion stacks and temporary variables may still exist.

Adaptiveness and Online Processing

An adaptive algorithm benefits from existing order. Insertion sort, for example, is fast when an array is nearly sorted. An online algorithm can process items as they arrive, maintaining a valid partial result. These properties can be as important as asymptotic complexity in real systems.

3. Elementary Comparison Sorts

3.1 Selection Sort

Selection sort repeatedly selects the smallest remaining item and places it at the next output position.

selectionSort(A)
    for i ← 0 to length(A) − 2
        smallest ← i
        for j ← i + 1 to length(A) − 1
            if A[j] < A[smallest]
                smallest ← j
        swap A[i] and A[smallest]

Selection sort performs Θ(n²) comparisons regardless of input order and uses O(1) auxiliary space. The standard exchange version is not stable, although stable variants can be constructed by shifting elements rather than swapping. Its advantage is a small number of writes, which can matter when writes are expensive.

3.2 Insertion Sort

Insertion sort maintains a sorted prefix. Each new element is shifted left until it reaches its correct position.

insertionSort(A)
    for i ← 1 to length(A) − 1
        value ← A[i]
        j ← i − 1
        while j ≥ 0 and A[j] > value
            A[j + 1] ← A[j]
            j ← j − 1
        A[j + 1] ← value

Insertion sort is stable, in-place, and online. Its worst-case and average-case time complexity is Θ(n²), but its best-case complexity is Θ(n) when the input is already sorted. If the number of inversions is small, its running time is close to linear. It is therefore useful for small arrays and as a finishing method within hybrid algorithms.

3.3 Bubble Sort

Bubble sort repeatedly compares adjacent items and exchanges inverted pairs. A pass moves a large item toward the end of the unsorted region.

With a flag indicating whether any exchange occurred, bubble sort can terminate early when the sequence is sorted. It is stable and in-place, but its average and worst-case complexity is Θ(n²). In professional software it is generally less useful than insertion sort, though it remains valuable pedagogically because it illustrates local exchanges and inversion reduction.

4. Efficient Comparison Sorts

4.1 Merge Sort

Merge sort uses divide and conquer. It divides the array into two halves, recursively sorts each half, and merges the sorted halves.

mergeSort(A, left, right)
    if right − left ≤ 1
        return
    middle ← floor((left + right) / 2)
    mergeSort(A, left, middle)
    mergeSort(A, middle, right)
    merge the sorted ranges A[left..middle) and A[middle..right)

The recurrence for a balanced merge sort is:

Here, n is the number of elements, the two recursive calls sort halves, and Θ(n) represents the merge. The resulting time complexity is Θ(n log n) in the best, average, and worst cases. Standard array merge sort requires Θ(n) auxiliary space and is stable when equal elements from the left half are chosen before equal elements from the right half.

Merge sort is attractive when predictable performance and stability are required. External merge sort is especially important when data does not fit in main memory: sorted runs are created on disk and then merged with sequential I/O.

4.2 Quicksort

Quicksort selects a pivot, partitions the array around that pivot, and recursively sorts the resulting regions. A partition operation places elements less than the pivot on one side and larger elements on the other, according to the chosen partition convention.

quickSort(A, low, high)
    if low < high
        p ← partition(A, low, high)
        quickSort(A, low, p − 1)
        quickSort(A, p + 1, high)

With balanced partitions, quicksort has Θ(n log n) time. If each partition places the pivot at an extreme, the recurrence becomes:

which gives Θ(n²). Randomized pivot selection, median-of-three heuristics, and three-way partitioning reduce the likelihood or impact of poor partitions, but ordinary quicksort is not stable and recursive calls require stack space. Careful implementations recurse first on the smaller partition and process the larger partition iteratively, limiting stack depth.

Three-way partitioning separates values into less-than, equal-to, and greater-than regions. It is particularly effective when many duplicate keys occur because the equal region needs no further sorting.

4.3 Heap Sort

A binary max-heap is a complete binary tree in which every parent is at least as large as its children. In an array representation using zero-based indexing, the children of node i are at indices 2i + 1 and 2i + 2 when those indices exist.

Heap sort first builds a heap and then repeatedly exchanges the maximum element with the last unsorted position, restoring the heap property each time. Building the heap takes Θ(n), and n removals take Θ(n log n), so the total complexity is Θ(n log n) in all cases. Heap sort is in-place but not stable.

Heap sort provides a strong worst-case guarantee and constant auxiliary storage. However, its memory-access pattern is less cache-friendly than that of some quicksort implementations, so practical performance depends on the environment.

5. Non-Comparison Sorting

Comparison sorts determine order only by comparing keys. Their performance is subject to a general lower bound. Non-comparison methods exploit additional information about keys, such as bounded integer ranges or digit representations.

5.1 Counting Sort

Counting sort is suitable when keys are integers in a manageable range from 0 through k. It counts each key, computes cumulative positions, and places records into an output array.

Its time complexity is O(n + k), and its auxiliary space is O(n + k) for the stable version, where n is the number of records and k is the maximum key value or range parameter. It is not appropriate when k is enormously larger than n. A stable implementation processes the input in a direction consistent with the cumulative-position scheme, commonly from right to left.

5.2 Radix Sort

Radix sort processes keys digit by digit, using a stable sorting method at each digit position. For d digits and radix b, a common complexity is O(d(n + b)), assuming each digit pass uses counting sort. The method is effective for fixed-width integers, identifiers, and strings when the digit representation is well defined.

Stability of the intermediate digit sort is essential for least-significant-digit-first radix sort. Without stability, ordering established by earlier digit passes can be destroyed.

5.3 Bucket Sort

Bucket sort distributes values into intervals, sorts each bucket, and concatenates the buckets. Under an assumption such as independent values uniformly distributed over a known interval, its expected time can approach Θ(n). In the worst case, all values may fall into one bucket, producing the performance of the bucket’s internal sorting method. Thus its efficiency depends strongly on the distribution assumption.

6. The Comparison-Sorting Lower Bound

For n distinct elements, any comparison sort can be represented by a decision tree. Each comparison has at most two outcomes relevant to ordering, while the n elements have n! possible input permutations. Therefore the tree must have at least n! leaves and height h satisfying:

Taking logarithms gives:

The notation Ω(n log n) means that, asymptotically, at least a constant multiple of n log n comparisons is required in the worst case. This lower bound applies to comparison-based sorting and does not contradict counting sort or radix sort, because those methods use information beyond pairwise comparisons.

The bound also explains why improving a comparison sort from Θ(n log n) to asymptotically linear time is impossible without adding assumptions about the keys or changing the problem.

7. Partitioning and Selection

7.1 Order Statistics

The kth order statistic is the kth smallest item when the data is arranged in nondecreasing order. The minimum is the first order statistic, the maximum is the nth, and the median is the middle order statistic. For even n, a definition is required: a system may select either middle item or define the median as the average of the two middle numerical values.

Sorting gives all order statistics in Θ(n log n), but finding only one rank may be done more efficiently.

7.2 Quickselect

Quickselect uses the same partitioning idea as quicksort but recurses into only the partition containing the desired rank.

quickselect(A, low, high, k)
    if low = high
        return A[low]
    p ← partition(A, low, high)
    if k = p
        return A[p]
    else if k < p
        return quickselect(A, low, p − 1, k)
    else
        return quickselect(A, p + 1, high, k)

Here k is an index, not necessarily a one-based rank. With randomized pivots, quickselect has expected Θ(n) time but worst-case Θ(n²). It is generally in-place apart from recursion and is useful when only one or a few order statistics are required.

A deterministic linear-time selection method, often called median-of-medians, groups elements, finds a robust pivot, and guarantees that a constant fraction of elements is discarded at each stage. Its worst-case complexity is Θ(n), although its constants may make randomized quickselect faster in many practical settings.

7.3 Worked Example: Selecting the Third Smallest Item

Consider the array [9, 2, 7, 4, 6, 3, 8]. We seek the third smallest value, using zero-based index k = 2. Suppose partitioning around 6 produces:

[2, 4, 3] 6 [9, 7, 8]

The pivot occupies index 3 in the fully positioned array. Since k = 2 is smaller than 3, discard the pivot and the right partition. Partitioning [2, 4, 3] around 3 gives:

[2] 3 [4]

The pivot now occupies index 2 in the original index range, so the answer is 3. Notice that the entire array was not sorted; only the information needed to determine the selected rank was established.

8. Comparative Evaluation

The table assumes standard implementations and should not be interpreted independently of data characteristics. For example, O(n + k) is excellent when k is small but poor when the key range is huge.

9. Applied Case: Ranking Transaction Records

Background

Consider an illustrative financial-technology service that receives millions of transaction records each day. Each record contains a transaction identifier, customer identifier, timestamp, amount, and risk score.

Problem

The service must answer three different requests: display the 100 highest-risk transactions, preserve timestamp order when two transactions have the same risk score, and support repeated lookup by transaction identifier.

Analysis

A complete sort is unnecessary for the first request. A selection procedure can identify a cutoff for the top 100, after which only the relevant records need to be sorted for display. If the output must be stable with respect to timestamp, the final sorting method should be stable and should use timestamp as a secondary key.

Repeated identifier lookup should not scan the complete file. A hash table offers expected constant-time exact lookup, while a sorted index supports binary search and ordered range queries. The choice depends on whether range queries, persistence, and update behavior are required.

Approach and Solution

The system maintains an index by transaction identifier for exact lookup. It uses a bounded heap of size 100 while streaming records: a min-heap stores the current 100 highest-risk records, and a new record replaces the minimum when its risk score is higher. This requires O(n log 100) time and O(100) storage for the candidate set, rather than storing and sorting all records.

The selected records are then sorted using a stable algorithm by risk score descending and timestamp ascending. Equal risk scores therefore retain the required timestamp ordering. Validation tests include duplicate scores, fewer than 100 records, missing identifiers, and records arriving out of timestamp order.

Outcome and Learning Points

The design separates three tasks instead of forcing one algorithm to solve all of them. A heap supports top-k selection, stable sorting supports deterministic presentation, and an index supports lookup. The case illustrates that algorithm choice should reflect workload, key properties, memory limits, and output requirements—not merely the largest asymptotic expression.

10. Implementation and Professional Practice

Correctness should be tested with empty inputs, singleton inputs, duplicate keys, reverse-sorted inputs, already sorted inputs, extreme values, and very large inputs. Property-based tests can verify that the output is ordered and is a permutation of the input. For stable sorting, tests should attach an original-position field to equal-key records and verify that those positions remain ordered.

Production implementations should avoid needless copying, document whether indices or ranks are zero-based, protect against integer overflow, and define behavior for null or invalid keys. Recursion limits matter for quicksort and quickselect. Security-sensitive systems should consider adversarial inputs: predictable pivot rules can allow an attacker to manufacture worst-case quicksort behavior. Randomization, introspective sorting, input validation, and resource limits can reduce this risk.

AI and data-processing systems frequently sort and rank records, but model outputs do not remove the need for deterministic tie-breaking, auditability, and reproducibility. When rankings affect people—for example, fraud review, hiring, or credit decisions—developers should document the ranking key, tie policy, data provenance, and opportunities for review. Sorting is a technical operation, but its outputs can have governance and fairness consequences.

Chapter Summary

Searching locates records, while sorting arranges records and selection identifies a rank without necessarily arranging every item. Linear search needs no ordering and takes O(n) time in the worst case. Binary search takes O(log n) time on sorted random-access data but requires careful boundary handling.

Insertion, selection, and bubble sort provide simple quadratic methods with different practical properties. Merge sort offers stable Θ(n log n) performance at the cost of auxiliary memory. Quicksort is often fast in practice and has expected Θ(n log n) performance, but poor pivots can produce quadratic behavior. Heap sort provides Θ(n log n) worst-case performance and in-place operation. Counting, radix, and bucket sort can beat the comparison lower bound when their assumptions about keys or distributions hold.

Stability, in-place operation, adaptiveness, memory access, and worst-case guarantees are important design criteria. The comparison decision-tree argument establishes an Ω(n log n) lower bound for comparison sorting. Partitioning is central to quicksort and quickselect. Quickselect provides expected linear-time selection, while deterministic selection guarantees linear worst-case time. Effective professional design matches the algorithm to the workload, data representation, memory constraints, and governance requirements.

Key Terms

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

Binary search: Searches a sorted random-access sequence by repeatedly halving the search interval.

Sorting: Rearranging records according to an ordering relation.

Stability: Preservation of the relative order of records with equal keys.

In-place algorithm: Algorithm using limited auxiliary memory beyond the input representation.

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

Insertion sort: Sort that inserts each item into a sorted prefix.

Selection sort: Sort that repeatedly selects the next minimum or maximum item.

Merge sort: Stable divide-and-conquer sort based on merging sorted subarrays.

Quicksort: Partition-based recursive comparison sort.

Pivot: Element used to divide data during partitioning.

Partitioning: Rearranging data into regions relative to a pivot or criterion.

Heap sort: In-place sort based on a binary heap.

Counting sort: Integer-key sort based on frequency counts.

Radix sort: Sort that processes keys by digit or character positions.

Order statistic: Element having a specified rank in sorted order.

Quickselect: Partition-based algorithm for selecting one order statistic.

Decision tree: Model of the comparisons made by a comparison algorithm.

Lower bound: Asymptotic limit below which no algorithm in a specified model can operate.

Top-k selection: Identification of the k largest or smallest items.

Review Questions

Short Answer Questions

1. What precondition is required for binary search?
2. Define stability in the context of sorting.
3. Why can insertion sort be efficient on nearly sorted data?
4. What is the worst-case complexity of ordinary quicksort?
5. Why can counting sort outperform comparison sorts?

Long Answer Questions

1. Compare linear search and binary search in terms of preconditions, data structures, complexity, and practical use.
2. Explain merge sort, including its recurrence, stability, space requirement, and applications.
3. Describe quicksort partitioning and explain how poor pivot choices affect performance.
4. Compare merge sort, quicksort, and heap sort for a system requiring predictable performance and limited memory.
5. Explain the comparison-sorting lower bound using the decision-tree argument.

Analytical / Application Questions

1. A system must sort one million records by score while preserving the arrival order of equal scores. Which algorithmic properties should guide the choice, and which method would you recommend?
2. A service must repeatedly return the 50 largest values from a stream that cannot fit in memory. Design an approach and analyze its space and time behavior.
3. Given a collection of integer keys in the range 0 through 999 and a very large number of records, compare counting sort with merge sort and justify a choice.

Multiple Choice Questions with Answers

Question 1

Which condition is necessary for standard binary search on an array?

A. The array must be sorted

B. The array must contain distinct values

C. The array must be stored as a linked list

D. The array must have a power-of-two length

Correct Answer: A. The array must be sorted

Question 2

What is the worst-case time complexity of linear search?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 3

Which sorting algorithm is stable in its standard form?

A. Heap sort

B. Insertion sort

C. Selection sort

D. Typical in-place quicksort

Correct Answer: B. Insertion sort

Question 4

What is the worst-case time complexity of merge sort?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: C. Θ(n log n)

Question 5

Why can comparison sorting not generally achieve o(n log n) worst-case comparisons?

A. Arrays cannot be indexed

B. The decision tree must distinguish n! permutations

C. Every comparison takes n operations

D. Sorting always requires an auxiliary array

Correct Answer: B. The decision tree must distinguish n! permutations

Question 6

Which feature distinguishes quickselect from quicksort?

A. Quickselect uses no comparisons

B. Quickselect recursively processes only the partition containing the desired rank

C. Quickselect always sorts the complete input

D. Quickselect requires the input to be sorted

Correct Answer: B. Quickselect recursively processes only the partition containing the desired rank

Question 7

Counting sort is most appropriate when:

A. Keys are arbitrary objects with no representation

B. The key range is manageable relative to the number of records

C. The input is stored only on a linked list

D. Stable ordering is impossible to define

Correct Answer: B. The key range is manageable relative to the number of records

Question 8

What is the worst-case time complexity of heap sort?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: D. Θ(n log n)

Question 9

In a zero-based array, which indices are the children of heap node i?

A. i − 1 and i + 1

B. 2i and 2i + 1

C. 2i + 1 and 2i + 2

D. i ÷ 2 and i ÷ 2 + 1

Correct Answer: C. 2i + 1 and 2i + 2

Question 10

A stable final sort is especially important when:

A. All keys are guaranteed distinct

B. Equal-key records must preserve a previous ordering

C. The input contains no records

D. Only the minimum value is required

Correct Answer: B. Equal-key records must preserve a previous ordering