10. Searching, Sorting, and Selection

Introduction and Context

Searching, sorting, and selection are among the most frequently used operations in computer science. A database index locates records, a compiler organizes symbols, a web service ranks results, and an operating system maintains ordered information. Although these operations may appear simple, their design involves important questions about time complexity, memory use, data distribution, stability, adaptiveness, scalability, and implementation environment.

Searching determines whether an item exists and, if so, where it is located. Sorting rearranges items according to a specified ordering relation. Selection identifies an item by rank, such as the minimum, maximum, median, or kth smallest element. These operations are closely related: sorting makes repeated searching and selection easy, whereas specialized searching and selection algorithms may avoid the cost of completely sorting the data.

This chapter develops these ideas through C-oriented algorithms and analysis. It compares linear and binary search, examines comparison and non-comparison sorting, explains order statistics, and introduces external sorting for data sets that do not fit in main memory. The emphasis is not only on writing algorithms but also on choosing an appropriate method for a particular data scale and application.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Implement and analyze linear and binary search in C.

2. Explain the operation and complexity of major comparison-based sorting algorithms.

3. Distinguish stable, unstable, adaptive, in-place, and non-in-place algorithms.

4. Apply counting sort, radix sort, and bucket sort when their assumptions are satisfied.

5. Find order statistics using sorting and selection algorithms.

6. Explain the lower bound for comparison-based sorting.

7. Describe external merge sorting for data larger than available memory.

8. Select algorithms using data size, key characteristics, memory limits, and application requirements.

Searching: Locating Information Efficiently

A search problem consists of a collection of records, a search key, and a rule for deciding whether a record matches the key. The collection may be unsorted, sorted, linked, indexed, or stored externally. The choice of search algorithm depends primarily on whether order is available and whether searches are performed once or repeatedly.

Linear Search

Linear search examines elements sequentially until the target is found or the collection is exhausted. For an array `a` of length `n`, its iterative C implementation is:

```c

int linearSearch(const int a[], int n, int key) {

for (int i = 0; i < n; ++i)

if (a[i] == key)

return i;

return -1;

}

```

If the first element matches, the algorithm performs one comparison. If the target is absent, or occurs at the final position, it performs `n` comparisons. Thus, the best-case complexity is O(1), while the worst-case and conventional average-case complexity are O(n). The algorithm requires O(1) additional space.

Linear search is not merely a beginner's method. It is appropriate for very small collections, unsorted data, linked lists, and situations in which sorting or indexing would cost more than the search itself. A useful refinement is the sentinel technique, in which the target is temporarily placed at the end of an array to reduce loop-bound checks. Such low-level optimizations should be adopted only after correctness and actual performance requirements are understood.

Binary Search

Binary search requires a sorted, random-access sequence. It compares the target with the middle element and discards the half that cannot contain the target. A safe iterative implementation is:

```c

int binarySearch(const int a[], int n, int key) {

int low = 0, high = n - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (a[mid] == key) return mid;

if (a[mid] < key) low = mid + 1;

else high = mid - 1;

}

return -1;

}

```

The expression `low + (high - low) / 2` avoids the potential integer overflow associated with `(low + high) / 2`. Binary search takes O(log n) time and O(1) iterative space. Its value becomes especially clear when many queries are made against a stable, sorted data set.

A common requirement is to find the first or last occurrence of a duplicate key. This is done by continuing the search after a match: for the first occurrence, record the middle position and continue in the left half; for the last occurrence, continue in the right half. Binary search can also find insertion positions, lower bounds, and upper bounds, which are fundamental operations in ordered collections.

Binary search is unsuitable for an ordinary linked list because reaching the middle requires traversal. Although the logical algorithm remains logarithmic in the number of elements, physical access may make the implementation inefficient. Balanced search trees or indexes are more appropriate when data changes frequently or is not stored contiguously.

Sorting as an Organizing Operation

Sorting transforms a sequence into nondecreasing or nonincreasing order according to a comparator. A sorting algorithm is evaluated by time complexity, auxiliary memory, stability, adaptiveness, implementation complexity, and suitability for the key type.

A sorting algorithm is stable if records with equal keys retain their original relative order. Stability matters when records contain secondary information or when sorting is performed in stages. An in-place algorithm uses only a small, usually O(1), amount of extra memory beyond the input array. An adaptive algorithm benefits from existing order. An algorithm is online if it can process items incrementally without requiring the complete input in advance.

Insertion Sort

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

```c

void insertionSort(int a[], int n) {

for (int i = 1; i < n; ++i) {

int value = a[i], j = i - 1;

while (j >= 0 && a[j] > value) {

a[j + 1] = a[j];

--j;

}

a[j + 1] = value;

}

}

```

Insertion sort is stable, in-place, and adaptive. Its worst-case time is O(n²), but its best-case time is O(n) when the input is already sorted. It is effective for small arrays and is often used inside sophisticated algorithms for small subarrays. The use of `>` rather than `>=` preserves stability.

Selection Sort

Selection sort repeatedly chooses the smallest remaining element and places it at the next output position. It performs O(n²) comparisons regardless of input order and uses O(1) extra space. The standard exchange version is generally not stable, although stable variants exist with additional shifting. Its advantage is a small number of writes, making it useful in unusual settings where writes are substantially more expensive than comparisons.

Bubble Sort

Bubble sort repeatedly exchanges adjacent elements that are out of order. With a flag indicating whether any exchange occurred, it can terminate early on sorted data. It is stable and adaptive in this optimized form, but its average and worst-case time remain O(n²). Its educational value is greater than its practical value for large inputs.

Merge Sort

Merge sort divides the array into two halves, recursively sorts each half, and merges the sorted halves. Merging takes linear time, giving the recurrence

`T(n) = 2T(n/2) + O(n)`,

and therefore O(n log n) time in the best, average, and worst cases. It is stable when equal elements from the left half are selected before equal elements from the right half. Array-based merge sort usually requires O(n) auxiliary space, while linked-list merge sort can merge efficiently by relinking nodes.

Merge sort is particularly important for external sorting because merging can be performed sequentially on files. It also provides predictable performance, unlike some simple implementations of quicksort.

Quicksort

Quicksort selects a pivot, partitions elements into smaller and larger groups, and recursively sorts the groups. Its average time is O(n log n), but an unbalanced sequence of partitions can produce O(n²) time. Randomized pivot selection, median-of-three strategies, and three-way partitioning reduce the likelihood or impact of poor partitions.

Quicksort is usually in-place and often fast in practice because of good cache behavior. Standard two-way partitioning is not inherently stable. Three-way partitioning is particularly useful when many elements equal the pivot, producing groups less than, equal to, and greater than the pivot. Recursion depth must also be controlled; a practical implementation can recurse on the smaller partition first and process the larger one iteratively.

Heap Sort

Heap sort builds a binary heap and repeatedly removes the maximum or minimum element. Building a heap takes O(n), and each of n removals takes O(log n), producing O(n log n) worst-case time. It uses O(1) auxiliary space and is not stable. Heap sort is valuable when a guaranteed time bound and small memory overhead are more important than average-case speed or stability.

Comparison of Principal Comparison Sorts

Insertion, selection, bubble, merge, quicksort, and heap sort compare keys to determine order. Their suitability differs:

• Insertion sort: small or nearly sorted inputs; stable and adaptive.
• Merge sort: predictable performance, stability, linked structures, and external files.
• Quicksort: high practical speed and low auxiliary memory, with careful pivot management.
• Heap sort: guaranteed O(n log n) time with constant extra space.
• Selection sort: small inputs or situations with a high cost for writes.
• Bubble sort: mainly instructional or highly specialized nearly sorted cases.

The Lower Bound for Comparison Sorting

A comparison sort can be represented by a decision tree. For `n` distinct elements, there are `n!` possible input permutations, and a correct algorithm must distinguish among all of them. A binary comparison has at most two outcomes, so a decision tree of height `h` has at most `2^h` leaves. Therefore:

`2^h >= n!`,

which implies `h >= log2(n!) = Ω(n log n)` using Stirling's approximation. Thus no comparison-based sorting algorithm can have a better asymptotic worst-case bound than Ω(n log n). Merge sort, heap sort, and well-designed quicksort achieve O(n log n) under appropriate conditions.

This lower bound does not apply to non-comparison sorting because those algorithms exploit information about the representation of keys, such as bounded integer ranges or digits.

Non-Comparison Sorting

Counting Sort

Counting sort is appropriate when keys are integers in a manageable range, for example from 0 through `k`. It counts occurrences and reconstructs the output. Its time and space costs are O(n + k). It can be stable if cumulative counts are used to place items into an output array from right to left. Counting sort is unsuitable when `k` is extremely large relative to `n`, because the count array may waste substantial memory.

Radix Sort

Radix sort processes keys digit by digit, commonly from the least significant digit to the most significant digit. Each pass must use a stable sorting method, often counting sort. For `d` digits and radix `b`, the cost is O(d(n + b)). Radix sort can outperform comparison sorts for fixed-width integers or strings, but its performance depends on representation, digit extraction, memory access, and the number of passes.

Bucket Sort

Bucket sort distributes values into intervals, sorts each bucket, and concatenates the results. Its expected performance can approach O(n) when values are distributed reasonably uniformly and the bucket strategy is appropriate. In the worst case, all values may enter one bucket, reducing performance to that of the bucket's internal sorting method. Bucket sort is therefore distribution-sensitive rather than universally linear.

Selection and Order Statistics

The kth smallest element is an order statistic. The minimum is the first order statistic, the maximum is the nth, and the median is the middle order statistic. A direct method is to sort the entire array and return position `k - 1`, costing O(n log n). This is appropriate when the sorted order will also be used.

For a single order-statistic query, sorting may perform unnecessary work. The partition operation used by quicksort can be adapted into quickselect. After partitioning around a pivot, only the side containing the desired rank is processed. Quickselect has expected O(n) time but O(n²) worst-case time with poor pivots.

The median-of-medians algorithm provides deterministic linear worst-case selection. It divides elements into groups, commonly of five, finds group medians, recursively selects a pivot from those medians, and partitions around that pivot. The pivot is guaranteed to discard a constant fraction of the elements, leading to O(n) worst-case time. Although its constants may be higher than those of randomized quickselect, it is valuable when predictable guarantees are essential.

For very large data sets or streaming data, exact selection may be expensive. Approximate quantile algorithms summarize distributions using bounded memory. Their use requires an explicit error interpretation: an approximate median is meaningful only when its rank or value error is defined and acceptable to the application.

External Sorting

When a file exceeds available main memory, an in-memory algorithm cannot sort all records at once. External sorting is designed around sequential disk or storage access. The standard external merge-sort process has two phases.

First, the system reads as much data as fits in memory, sorts the block internally, and writes the sorted block as a run. This continues until the input is exhausted. Second, the sorted runs are merged. A k-way merge maintains one current element from each run in a min-heap, repeatedly outputs the smallest, and replaces it with the next element from the corresponding run.

External performance is often measured in block transfers or I/O operations rather than CPU comparisons. Sequential access is usually much cheaper than random access, so larger runs and efficient multiway merging reduce the number of passes. The number of initial runs, available buffers, and merge fan-in affect performance. Stability may be preserved by including original sequence numbers as tie-breakers.

External sorting appears in database systems, log processing, scientific data analysis, and large-scale data pipelines. Modern distributed systems extend the idea through partitioning, local sorting, and distributed merging, but the central principle remains: exploit sequential processing and minimize data movement.

An Applied Case: Ranking a University Examination Archive

Background

A university maintains eight million examination records. Each record contains student identifier, course code, semester, marks, and a submission sequence number. The administration must support two operations: frequent queries for all records of a course ordered by marks, and occasional computation of the median mark for a course.

Situation and Analysis

The complete archive cannot be reliably sorted in memory on the available server. Furthermore, records with equal marks must retain submission order for auditability. A one-time linear search would be inadequate for repeated course queries, while sorting the entire archive for every median request would be wasteful.

Approach

The archive is first externally sorted by course code and marks, with submission sequence as a tie-breaker. Stable ordering or an explicit sequence field preserves audit order. Course boundaries are indexed, allowing binary search to locate the beginning and end of a course segment. Within a selected course, the median can be obtained directly from the ordered segment. If medians were required before permanent ordering was created, a selection algorithm could be applied separately to each in-memory course partition.

For new records, a batch pipeline creates sorted runs and periodically merges them. Validation checks confirm that comparison fields are correctly typed, missing marks are handled by policy, and duplicate identifiers do not silently replace records.

Outcome

Repeated course queries use logarithmic boundary searches followed by sequential retrieval. The archive is processed with bounded memory, and stable tie handling supports audit requirements. The design avoids using counting sort merely because marks are integers: counting sort might be useful for a small fixed mark range, but it would not itself organize the other record fields or solve external-memory constraints.

Learning Points

The case demonstrates that algorithm choice depends on the complete workload. Binary search is valuable after an ordering has been established; external merge sort is selected because the data exceeds memory; stability is a functional requirement; and selection is preferable to full sorting when only a rank is needed.

Common Errors, Risks, and Design Decisions

A frequent error is applying binary search to unsorted data or modifying the collection without maintaining the ordering invariant. Another is writing a midpoint calculation that can overflow, or returning an arbitrary duplicate when the application requires the first occurrence. Sorting errors include confusing stable output with sorted output, using counting sort with an impractically large range, and assuming quicksort always has O(n log n) worst-case time.

Algorithmic complexity is not the only performance measure. Cache locality, branch behavior, record size, memory bandwidth, storage latency, and input distribution can dominate in real systems. A stable algorithm may require additional memory, while an in-place algorithm may be less suitable for parallel or external processing. Requirements should therefore be stated explicitly before implementation.

Input validation is also a professional responsibility. Integer overflow in index calculations, malformed keys, duplicate records, and inconsistent comparison functions can produce incorrect results or security vulnerabilities. A comparator must define a consistent ordering; violations can make sorting behavior unpredictable. Test cases should include empty arrays, one-element arrays, duplicates, already sorted and reverse-sorted inputs, extreme values, and very large records.

Technology and Emerging Practice

Standard libraries often provide highly optimized sorting functions, and production software should normally use them unless a specialized requirement justifies a custom implementation. Parallel sorting divides data into partitions, sorts them concurrently, and merges the results. GPUs and vector processors can accelerate regular operations such as radix passes, although irregular comparisons may reduce their advantage.

Data systems increasingly use external-memory and distributed sort operators. Approximate selection and quantile summaries support dashboards and monitoring when exact answers are unnecessary. Machine-learning pipelines also depend on sorting and ranking, but automated systems must document tie rules, missing-value policies, and whether ranking decisions create fairness or governance concerns. Algorithmic efficiency does not remove the obligation to protect personal data and restrict access to sensitive records.

Best Practices for Algorithm Selection

Begin by identifying the operation: one search, repeated search, complete ordering, minimum or kth element, or large-file processing. Then characterize the data: sortedness, duplicates, key range, distribution, record size, and update frequency. Finally, evaluate memory, stability, worst-case guarantees, and I/O behavior.

For a small unsorted collection, linear search is often simplest. For repeated queries over stable sorted data, binary search or an index is appropriate. Use insertion sort for small or nearly sorted arrays, merge sort when stability and predictable performance matter, quicksort or an introspective hybrid for fast in-memory general sorting, and heap sort when worst-case guarantees with low extra memory are important. Use counting or radix methods only when key representation makes their assumptions valid. Use external merge sort when the input exceeds memory.

Chapter Summary

Searching, sorting, and selection are fundamental operations whose best algorithms depend on data organization and workload. Linear search requires no ordering and takes O(n) worst-case time; binary search requires sorted random access and takes O(log n). Comparison sorting is subject to an Ω(n log n) lower bound, while non-comparison methods can be faster when keys have restricted representations. Insertion sort is stable and adaptive for small or nearly ordered inputs; merge sort offers stable predictable performance; quicksort is often fast but requires protection against poor partitions; and heap sort provides an O(n log n) worst-case guarantee with constant auxiliary space. Counting, radix, and bucket sorting exploit key properties. Quickselect and median-of-medians address order statistics without necessarily sorting all data. External merge sort extends sorting to files larger than memory by generating and merging sorted runs. Practical choices must consider stability, memory, distribution, I/O, correctness, and professional governance requirements.

Key Terms

Linear search: Sequential examination of elements until a match is found or the collection ends.

Binary search: A search method that repeatedly halves a sorted random-access range.

Comparator: A function or rule that defines the ordering of records.

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

In-place algorithm: An algorithm using only a small amount of additional memory beyond its input.

Adaptive algorithm: An algorithm whose performance improves when the input already has useful order.

Insertion sort: A stable, in-place method that inserts each item into a sorted prefix.

Merge sort: A divide-and-conquer sort based on recursively sorting and merging subarrays.

Quicksort: A partition-based recursive sorting algorithm using a pivot.

Heap sort: A sorting algorithm that repeatedly extracts elements from a heap.

Counting sort: An integer sorting method that counts occurrences within a key range.

Radix sort: A digit-by-digit sorting method using a stable sort at each digit position.

Bucket sort: A distribution-based method that sorts elements within value intervals.

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

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

Decision tree: A model representing the comparison outcomes of a comparison algorithm.

External sorting: Sorting designed for data that does not fit in main memory.

Run: A sorted block produced during the initial phase of external sorting.

K-way merge: A merge of k sorted sequences, commonly managed with a min-heap.

Quantile: A value or rank dividing an ordered distribution according to a specified proportion.

Review Questions

Short Answer Questions

1. Why does binary search require sorted random-access data?

2. Define stability in sorting and give one practical reason it matters.

3. State the best-case and worst-case time complexities of insertion sort.

4. What is an order statistic?

5. Why is external merge sort suitable for files larger than main memory?

Long Answer Questions

1. Explain linear and binary search, including their assumptions, C implementation issues, and complexity.

2. Compare insertion sort, merge sort, quicksort, and heap sort with respect to time, space, stability, and use cases.

3. Derive the Ω(n log n) lower bound for comparison-based sorting using a decision-tree argument.

4. Explain counting sort, radix sort, and bucket sort, including the assumptions that make each effective.

5. Describe the two phases of external merge sort and explain how buffering and k-way merging affect performance.

Analytical / Application Questions

1. A sorted array contains many duplicate keys, and an application needs the first occurrence of a target. How should binary search be modified, and what is its complexity?

2. A system needs the 90th percentile of ten million in-memory values but does not need the complete sorted sequence. Compare full sorting, quickselect, and deterministic selection.

3. You must sort records larger than memory while preserving the input order of equal keys. Design an algorithm and explain how stability can be maintained during external merging.

22. Multiple Choice Questions with Answers

Question 1

Which condition is essential for the standard binary search algorithm on an array?

A. The array must contain distinct values

B. The array must be sorted and support efficient random access

C. The array must have a length that is a power of two

D. The array must be stored in descending order only

Correct Answer: B. The array must be sorted and support efficient random access

Question 2

Which sorting algorithm is both stable and adaptive in its standard array implementation?

A. Heap sort

B. Selection sort

C. Insertion sort

D. Unoptimized quicksort

Correct Answer: C. Insertion sort

Question 3

Why can a comparison-based sorting algorithm not have a better general worst-case bound than Ω(n log n)?

A. Every comparison requires constant memory

B. There are n! possible input permutations to distinguish

C. Arrays cannot contain duplicate values

D. All sorting algorithms use recursion

Correct Answer: B. There are n! possible input permutations to distinguish

Question 4

For which situation is counting sort most appropriate?

A. Keys are arbitrary large strings

B. Keys are integers with a manageable range

C. Records are stored only in a linked list

D. The input distribution is unknown and unbounded

Correct Answer: B. Keys are integers with a manageable range

Question 5

What is the expected time complexity of quickselect for one order statistic?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n) always

Correct Answer: C. O(n)

Question 6

Which statement about quicksort is correct?

A. Its worst-case time is always O(n log n)

B. It is inherently stable

C. Poorly balanced partitions can lead to O(n²) time

D. It cannot be implemented in-place

Correct Answer: C. Poorly balanced partitions can lead to O(n²) time

Question 7

A file is larger than available main memory. What is the standard strategy in external merge sort?

A. Perform binary search on the unsorted file

B. Create sorted runs and merge them

C. Use selection sort on the complete file in memory

D. Discard duplicate records before sorting

Correct Answer: B. Create sorted runs and merge them

Question 8

Which property is required at every pass of a least-significant-digit radix sort to preserve the final ordering?

A. The pass must use an unstable algorithm

B. The pass must use a stable sorting method

C. The pass must compare complete records

D. The pass must use random pivot selection

Correct Answer: B. The pass must use a stable sorting method

Question 9

If an application needs only the minimum of an unsorted array, which approach generally avoids unnecessary work?

A. Sort the entire array with merge sort

B. Use a linear scan maintaining the smallest value

C. Use binary search immediately

D. Build a complete radix index regardless of key type

Correct Answer: B. Use a linear scan maintaining the smallest value

Question 10

Which design choice helps prevent integer overflow when computing a binary-search midpoint?

A. Use `(low + high) / 2` unconditionally

B. Use `low + (high - low) / 2`

C. Always set the midpoint to zero

D. Use floating-point comparison for every key

Correct Answer: B. Use `low + (high - low) / 2`