Searching, Sorting and Efficiency

Searching asks whether a target occurs and where it occurs. A list has numbered positions called indexes. Python counts from zero: in [7, 3, 9, 3, 5], index 0 holds 7, and index 4 holds 5. The value and its index answer different questions.

Check one item at a time

Linear search, also called sequential search, starts at the first item and compares each item with the target. It returns immediately when it finds a match. If the list ends without a match, it returns -1, our signal for “not found.”

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

len(items) gives the number of items. range(len(items)) supplies every valid index, starting at 0 and ending just before the length. items[i] reads the value at the current index. A return ends the function, so a later match never replaces the first one.

Searching the list above for 3 proceeds as follows:

1. At index 0, compare 7 with 3. They differ, so continue.
2. At index 1, compare 3 with 3. They match, so return index 1.

The result is index 1 after two comparisons. The second 3, at index 3, is never checked. Searching for 4 instead checks 7, 3, 9, 3, and 5, then returns -1 after five comparisons. A returned index of 1 means the second item, not an item whose value is 1.

Count the work

Let $n$ be the number of items. For a nonempty list, the best case is one comparison: the first item matches. The worst case is $n$ comparisons: the target is last or absent. An empty list needs zero comparisons and returns -1.

If a target occurs once and is equally likely to occupy any position, its average comparison count is

For 1,000 items, that is 500.5 comparisons. An average can be fractional even though every individual search makes a whole number of comparisons. This average describes that particular distribution of successful searches; frequent unsuccessful searches would increase the overall average.

Put failure after the loop

An else: return -1 inside the loop would give up at the first mismatch. On [7, 3, 9], it would reject a search for 3 after seeing only 7. The failure return belongs after the loop, when every position has been ruled out.

Linear search needs no sorted order or preparation. It works with numbers, words, or records compared by an ID. A version designed for sorted data can stop when it passes the target's possible position: in [2, 5, 8, 12], seeing 8 is enough to rule out 6. The code above deliberately keeps scanning until it finds a match or reaches the end.

Related tasks use the same scan but a different stopping rule. Counting every occurrence, collecting every matching index, and finding a largest item all require inspecting the full list; finding the first match permits an early return.

Binary search uses sorted order to discard positions without checking them individually. Its input must be sorted in ascending order. It also needs quick access to an item at a chosen index, as an array or Python list provides.

Keep an inclusive range

low and high mark the first and last positions still possible, including both endpoints. Start with low = 0 and high = len(items) - 1. Choose the middle index by rounding down. If the middle value is too small, every value to its left is also too small; move low past the middle. If it is too large, move high just before it.

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

// divides and rounds down. The loop includes the case low == high because one unchecked position remains. When low > high, the range is empty.

Trace a match and a miss

Use [3, 8, 12, 17, 23, 31, 42, 56, 64, 77, 85], indexed 0 through 10. To find 64, the first middle index is 5, holding 31. Since 31 is too small, set low = 6. The next middle index is 8, holding 64. Return 8 after two middle-item checks.

To search for 20 in the same list:

Now the range is empty, so return -1. This is a reasoned failure: sorted order justified every discarded part.

Why it is fast

Each unsuccessful check leaves at most half the range. For a nonempty list, the maximum number of middle-item checks is $\lfloor {\log }_{2}n\rfloor +1$. The base-2 logarithm describes repeated halving: $2^{10}=\mathrm{1,024}$, so a thousand items need at most 10 checks; a million need at most 20. One check in this Python code can make two comparisons, == and <. Checks and comparisons are different counting units.

Conditions and boundary bugs

Sorted order is essential. Searching [9, 2, 7, 4, 1] for 2 first sees 7 and discards the right part, then sees 9 and discards the remaining match at index 1. Quick middle access matters too: following links to reach a linked list's middle loses the array version's speed advantage.

Always exclude the tested middle after a mismatch. Using low = mid can leave [10, 20] unchanged forever when searching for 20. Using while low < high skips the final candidate and fails on [5] searched for 5. On an empty list, high = -1, so the correct loop never starts.

With duplicates, this version returns any matching index. Searching [2, 4, 4, 4, 9] for 4 returns index 2 immediately; finding the first occurrence requires a modified search that continues left after a match.

Sorting rearranges items by a chosen key. For numbers in ascending order, each item is less than or equal to the next. “Non-decreasing” makes room for equal neighbors: [2, 5, 5, 9] is sorted. Descending order reverses the direction.

Check two conditions

A correct sort must produce ordered output containing exactly the original items, with every repetition preserved. Sorting [3, 1, 2] into [1, 2, 3] succeeds. Both [1, 2] and [1, 1, 3] fail, even though their neighbors are in order. The first loses an item; the second changes which items occur. A rearrangement preserving all occurrences is called a permutation.

For a record, the key is only the field used for comparison. Cities could be sorted by name or population. The whole city record moves when its population key moves; detaching the name would corrupt the data.

Text order depends on the key

Plain text comparison follows character codes, one character at a time. In ASCII and Unicode, A–Z use codes 65–90 and a–z use 97–122. This puts “Zebra” before “apple” in a plain comparison. Comparing lowercase copies can provide case-insensitive order for these examples.

Text digits also behave as characters. “10” sorts before “9” because its first character is “1.” A numeric key converts those strings to the numbers they represent, giving 9 before 10. Decide what the data means before choosing the comparison.

Move values without losing them

A swap exchanges two positions. A temporary variable protects the value that would otherwise be overwritten:

temp = items[i]
items[i] = items[j]
items[j] = temp

Python also allows items[i], items[j] = items[j], items[i]. Writing the two assignments without saving the first value changes [4, 7] into [7, 7]. Bubble and selection sort move items by swapping; merge sort copies items into merged output.

Stability and memory

A stable sort keeps the original order of records whose keys are equal. Start with Ana 85, Ben 92, Cara 85, in alphabetical order. A stable descending score sort produces Ben 92, Ana 85, Cara 85. Ana remains before Cara. This lets a later sort by score retain an earlier alphabetical order within each score group. Python's built-in sorting is stable.

An in-place sort rearranges the existing list with only a few extra variables, independent of its length. The bubble and selection methods taught here are in place. The usual merge sort needs extra storage proportional to the number of items. Stability and memory describe different properties: a sort can be in place yet unstable.

Measure disorder with inversions

An inversion is a pair of positions where an earlier item's key is greater than a later one's. In [5, 1, 4, 2, 8], the inversions are (5, 1), (5, 4), (5, 2), and (4, 2): four in all. Pairs need not be neighbors.

A sorted list has zero inversions. A reversed list of $n$ distinct items has $n(n-1)\mathrm{/}2$, the maximum. Equal keys never form an inversion: [3, 3, 1] has two, one for each 3 before 1. Counting inversions is useful when explaining bubble sort's swap count.

Bubble sort compares neighboring items from left to right. When the left item is larger, it swaps the pair. Each sweep is a pass. A large item can move right repeatedly during one pass, until the largest remaining item reaches its final position.

Follow the first pass

Start with [5, 1, 4, 2, 8]:

1. Compare 5 and 1; swap to get [1, 5, 4, 2, 8].
2. Compare 5 and 4; swap to get [1, 4, 5, 2, 8].
3. Compare 5 and 2; swap to get [1, 4, 2, 5, 8].
4. Compare 5 and 8; leave them alone.

The pass makes four comparisons and three swaps. The largest item, 8, is settled. The rest is still unsorted: 4 precedes 2. One pass guarantees the final position of the maximum, not the order of every item.

Pass 2 needs only the first four positions. Compare 1 with 4, then swap 4 with 2, then compare 4 with 5. This gives [1, 2, 4, 5, 8] after three more comparisons and one swap. Pass 3 compares 1 with 2 and 2 with 4. It makes no swaps, confirming that the list is sorted. Totals: nine comparisons and four swaps.

Shorten each pass and stop early

def bubble_sort(items):
    n = len(items)
    for p in range(n - 1):
        swapped = False
        for j in range(n - 1 - p):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break

Pass counter p starts at zero. The largest value of j is n - 2 - p, so j + 1 stays inside the unsorted part. Reset swapped at the beginning of each pass; a swap on an earlier pass tells you nothing about whether the current pass moved an item.

After each pass, one more position at the right is final. A pass with no swaps proves all compared neighbors are in order. The already settled suffix is also in order, so the algorithm can stop. The confirming pass still counts as work.

Compare best and worst cases

For a sorted nonempty list, the early-stop version makes $n-1$ comparisons and zero swaps. On a reversed list of distinct items, it makes

comparisons and the same number of swaps. Five items need 10; 1,000 items need 499,500. Without early stopping, the five-item worked example would also run its final one-comparison pass, reaching 10 comparisons.

Each swap removes exactly one inversion. The four inversions in the original worked list explain its four swaps. Equal neighbors stay put because the test uses >, making this version stable and in place. Replacing > with >= can reverse equal-key records.

Position matters even when there are few inversions. [5, 1, 2, 3, 4] uses four swaps and a second pass to confirm order, for seven comparisons. [2, 3, 4, 5, 1] also needs four swaps, but its 1 can move left only once per pass. It needs all four passes and 10 comparisons.

Selection sort builds a sorted prefix on the left. Each pass finds the smallest item in the remaining suffix, then swaps it into the prefix's next position. The scan finds the position; the swap happens after the scan.

Remember an index

At position i, begin with smallest = i. Compare each later item with items[smallest]. Update smallest only when a smaller item appears. When the scan ends, exchange items[i] and items[smallest].

def selection_sort(items):
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]

Remembering only the smallest value would leave you without its position for the exchange. Starting the scan at index 0 would revisit the items already placed; the remaining search starts just after i.

Trace the passes

Start with [29, 10, 14, 37, 13].

The third minimum is already in position, so no values move. After four passes, the last item must be the largest; it needs no separate pass. There are 10 comparisons and three swaps that move items. The conditional in the code skips exchanges of a position with itself; omitting that conditional leaves the result unchanged.

Comparisons and swaps have different costs

Selection sort always makes $n(n-1)\mathrm{/}2$ item comparisons: every pass must inspect the entire remaining suffix to identify its minimum. The total is 10 for five items or 499,500 for 1,000, even on already sorted input. A scan that changes no remembered index establishes that pass's minimum, but gives no general guarantee that the remaining suffix is ordered.

For a nonempty list, there is at most one moving swap per pass, hence at most $n-1$ overall. Empty input needs no passes or swaps. Bubble sort can need $n(n-1)\mathrm{/}2$ swaps on a reversed list of distinct items. If moving large records costs much more than comparing their keys, selection sort's small swap count can matter despite its many comparisons. Swapping every time a new minimum appears during the scan loses that advantage.

Equal keys can change order

This swap-based method is in place but unstable. Label equal-key records 4a and 4b so their identity is visible. Starting with [4a, 4b, 1], the first pass exchanges 4a and 1, producing [1, 4b, 4a]. The equal keys have reversed their original order even though the algorithm never directly compared them as unequal. Keeping the first minimum found during a scan does not prevent a distant swap from crossing an equal-key record.

Merging combines two already sorted lists into one sorted output. Keep a marker at the first unused item of each input. Compare those two front items, copy the smaller one, and advance only its marker.

Choose the next smallest item

Merge [3, 27, 38, 43] with [9, 10, 82]:

The left list is now empty. Copy the remaining 82 without another item comparison. The result is [3, 9, 10, 27, 38, 43, 82], using six comparisons. Copying the tail is part of the algorithm: stopping when the comparisons stop would lose data.

Why can the method ignore items behind the fronts? Each front is the smallest remaining item of its own list. The smaller front is therefore the smallest remaining item overall. This reasoning continues after each marker moves because the unused portions remain sorted.

Read the merge code

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

append adds one item. A slice such as left[i:] contains the unused tail, and extend copies its items. Only one unused tail can be nonempty when the loop ends. If an input starts empty, the loop makes zero comparisons and the other list is copied intact.

Count comparisons and storage

For two nonempty lists of lengths $m$ and $k$, at most $m+k-1$ front comparisons are needed. Every comparison places one item, and at least the final item can be copied without comparing. The shortest possible merge comparison count is the length of the shorter list: [1, 2, 3] merged with [4, 5, 6] uses three comparisons before the left side empties.

The total copying work grows with $m+k$ even when comparisons finish early, because every item must appear in the output. The new list also needs room for $m+k$ items. Comparison count, copying work, and extra storage measure different parts of the same operation.

Handle ties and input order

The <= test takes from the left on equal keys. If the two inputs came from consecutive parts of an original list, this preserves the earlier record before the later equal-key record. It is the tie rule needed for stable merge sort.

The sorted-input requirement is firm. Merging [5, 1] with [3] copies 3, then the tail [5, 1], producing [3, 5, 1]. The front rule failed because 5 was not the smallest remaining value in its own input.

Merge sort solves a large sorting task by splitting it into smaller sorting tasks. This is divide and conquer: divide the list, sort each half, and merge the sorted halves.

Stop splitting at the base case

A function is recursive when it calls itself. Merge sort calls itself on shorter lists. Its base case returns a list of zero or one items unchanged, since such a list is already sorted.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

The slices divide the input without losing items. For an odd length, the right side has one more item: [6, 2, 9, 4, 1, 7, 3] splits into [6, 2, 9] and [4, 1, 7, 3]. Both halves are shorter, so recursive calls eventually reach the base case. A base case alone would not ensure termination if a call kept passing the original list back to itself.

Rebuild the sorted list

Trace [38, 27, 43, 3, 9, 82, 10, 15]. It splits into two four-item halves, then four two-item pieces, then single items. Splitting does not rearrange the values. Order is built during the merges:

1. Merge singletons into [27, 38], [3, 43], [9, 82], and [10, 15]. Each uses one comparison: four total.
2. Merge pairs into [3, 27, 38, 43] and [9, 10, 15, 82]. Each uses three comparisons: six total.
3. Merge those halves into [3, 9, 10, 15, 27, 38, 43, 82]. This uses seven comparisons.

The full sort uses $4+6+7=17$ item comparisons. Do not count only the final merge: the sorted halves had to be produced first. The seven-item example above sorts to [1, 2, 3, 4, 6, 7, 9] using 14 comparisons with this splitting rule.

Count levels and work per level

For eight items, halving reaches singletons after three levels because $2^3=8$. In general, there are about ${\log }_{2}n$ merge levels. Across a complete level, the merges collectively handle all $n$ items. Each level therefore does work proportional to $n$, leading to growth like $n{\log }_{2}n$.

For eight items, $n{\log }_{2}n=24$ is a useful loose comparison bound, not the exact count. The worked list used 17; an already sorted or reversed eight-item list uses 12. The input order changes when a merge exhausts one side, but every list still goes through the splitting and merging levels. The comparison growth remains $n\log n$ across best and worst cases for this version.

For a million items, about 20 levels give about 20 million comparisons as an upper-scale estimate. Selection sort uses about 500 billion. The difference grows rapidly with input size.

Pay for the extra output space

The ordinary list-based merge sort needs extra storage proportional to $n$. Choosing the left front on ties makes it stable.

A measured running time depends on the machine and program. A step count describes the algorithm's work using a chosen repeated operation. The input size, written $n$, is the number of items being processed.

Choose the operation before counting

For searching and sorting, comparisons between item values usually make a useful basic operation. Count swaps separately when moving data matters. For binary search, it is convenient to count checks of a middle item. In the Python version, an unsuccessful middle check evaluates both equality and less-than, so it can involve two item comparisons.

These counts describe repeated operations, not lines of code. One line inside a loop can execute a million times; several setup lines may each execute once.

Separate cases at the same size

The best case takes the fewest steps among valid inputs of size $n$. The worst case takes the most and supplies a guarantee. The average case averages over a stated pattern of inputs.

For a nonempty list, linear search needs one comparison if the target is first, and $n$ if it is last or absent. Its successful-search average is $(n+1)\mathrm{/}2$ when the first matching position is equally likely to be any position. The word “average” needs that distribution; it does not mean the midpoint of the best and worst counts for every algorithm.

Translate loops into counts

One comparison per item in a full scan gives $n$ comparisons. Two full nested loops, each running $n$ times, execute their shared body $n^2$ times. A different nested-loop pattern compares each pair only once:

for i in range(n):
    for j in range(i + 1, n):
        compare(items[i], items[j])

The first outer iteration compares its item with $n-1$ later items. The next compares with $n-2$, and the last compares with none. The total is

Write the sum forward and backward. Each aligned pair adds to $n$, and there are $n-1$ such pairs. Their total is $n(n-1)$, twice the original sum. For five items, $4+3+2+1=10$; for 1,000, the pair count is 499,500.

Recognize repeated halving

A loop that halves its remaining work takes about ${\log }_{2}n$ repetitions. One million first falls to 1 or below after 20 halvings: $2^{19}=\mathrm{524,288}$ and $2^{20}=\mathrm{1,048,576}$ straddle a million. This differs sharply from removing just one item each time.

For growth comparisons, keep the fastest-growing term. The pair count is $n^2\mathrm{/}2-n\mathrm{/}2$. At $n=\mathrm{1,000}$, its terms are 500,000 and 500, so the quadratic term controls the growth. Dropping the smaller term and the constant factor describes the growth family; it does not turn the exact count of 499,500 into an exact count of one million.

A growth rate describes how the amount of work changes as the input gets larger. It helps compare algorithms beyond the particular size used in one trace.

Read the common families

For exponential growth, adding just one item already doubles the count: $2^{n+1}=2\times 2^n$. Doubling the input is a much larger change than adding one.

Compare sizes numerically

For inputs of 10, 100, 1,000, and one million items, ${\log }_{2}n$ is about 3.3, 6.6, 10, and 20. The corresponding $n{\log }_{2}n$ values are about 33, 664, 9,966, and 20 million. The quadratic values are 100, 10,000, one million, and one trillion.

Logarithmic growth is not “half the list.” For a million items, halving repeatedly takes only about 20 stages. When input rises from 1,000 to 2,000, $n{\log }_{2}n$ rises from about 9,966 to 21,932, a factor of about 2.2. The logarithm changes too, so the count grows slightly faster than linear.

Exponential work becomes large quickly. $2^{10}=\mathrm{1,024}$ and $2^{20}$ is about a million. At a billion steps per second, $2^{50}$ steps still take about 13 days. Adding one more item doubles that time.

Use informal O labels

Programmers commonly label these families $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$, and $O(2^n)$. Here they identify the usual worst-case growth family. Read $O(n^2)$ as “order n squared.” The label suppresses constant factors and lower-order terms: $n(n-1)\mathrm{/}2$ comparisons belongs to the quadratic family.

An O label is not an exact running time or a number of seconds. It also does not claim that every input uses the worst-case count. Bubble sort with early stopping has a linear best case but a quadratic worst case.

Find the crossover

Suppose method A takes $100n$ steps and method B takes $n^2$. At 50 items, A takes 5,000 steps and B takes 2,500. At 100, both take 10,000. At 1,000, A takes 100,000 and B takes one million. A's slower growth eventually overcomes its larger constant factor.

Hardware speed changes the scale without changing the family. A computer 100 times faster gives a quadratic method room for only 10 times as many items in the same time, since $(10n{)}^2=100n^2$. A linear method could handle 100 times as many. For a small task, setup and constants may dominate; for large inputs, growth becomes decisive.

A known running time and a growth pattern let you predict how a larger task will behave. The prediction is an estimate because real time also depends on implementation, memory, hardware, and other work on the machine.

Scale the input, then the time

For linear work, multiply the time by the input-size ratio. If a worst-case search of one million items takes 3 milliseconds, ten million items take about 30 milliseconds under comparable conditions.

For quadratic work, square the ratio. Suppose selection sort takes 2 seconds for 50,000 items. Doubling to 100,000 items gives

seconds. Increasing to 500,000 items multiplies input size by 10, so the time estimate is $2\times {10}^2=200$ seconds. Scaling the time by 10 would incorrectly treat the algorithm as linear.

For $n{\log }_{2}n$ growth, use the ratio of both full expressions. Doubling a large input costs a little more than twice as much because the logarithm increases along with the item count.

Work backward from a time budget

Use the same quadratic baseline: 2 seconds for 50,000 items. A 32-second budget allows 16 times the time. The input can grow by the square root of 16, which is 4, giving about 200,000 items. Check the direction by substitution: four times the input predicts 16 times the time, taking 2 seconds to 32 seconds.

Compare algorithms at a large size

For one million items, selection sort makes 499,999,500,000 comparisons, about 500 billion. Merge sort needs at most about 20 million. At a hypothetical billion comparisons per second, those counts correspond to about 500 seconds versus 0.02 seconds, roughly a 25,000-fold difference. This calculation uses equal comparison cost to isolate the algorithmic effect; measured programs also pay for movement and memory access.

Test a growth prediction

Time the same program on several doubling sizes, such as 10,000, 20,000, and 40,000 items. Divide each time by the previous time. Ratios near 2 suggest linear growth; a little above 2 suggests $n\log n$; near 4 suggests quadratic growth.

Keep the machine and measurement method consistent. Repeat runs and use sizes large enough that startup time does not dominate. Compare like cases: searching at the first position at one size and searching unsuccessfully at another would mix input effects with growth. For bubble sort, sorted lists and reversed lists need different case labels.

If doubling sizes gives 0.04, 0.16, and 0.64 seconds, both ratios are 4, supporting a quadratic model over that range. One noisy ratio is weaker evidence than a repeated pattern. Step counts for a specified trace can be exact; a prediction in seconds should say “about” and be checked against measurements.

A correct algorithm stops on every valid input and produces the required output. A specification states the input condition and the promised result. For binary search, the precondition is ascending sorted order. The postcondition is a matching index, or -1 exactly when the target is absent.

Use an invariant to connect steps

A loop invariant is a statement that holds before the loop begins and is preserved by every repetition. A correctness argument checks its start, its preservation, and what it implies when the loop ends. Separately, a termination argument shows that the loop eventually ends.

For selection sort, use this invariant: before pass i, the first i positions contain the i smallest items in order.

1. Start: before pass 0, the prefix is empty. It already meets the statement.
2. Preserve: the pass finds the smallest remaining item. Putting it next extends the sorted prefix by one, and the item is at least as large as every previously placed item.
3. Finish: after at most $n-1$ passes, only the largest item remains outside the prefix. The whole list is sorted.

Every move is a swap, so the multiset of items also stays unchanged. Ordered output alone would not meet the full sorting specification.

Bubble sort uses a suffix invariant: after $k$ passes, the last $k$ positions contain the $k$ largest items in order. The next pass carries the largest unsorted item to that suffix. A pass with no swaps establishes order throughout the remaining part, allowing early termination.

Explain binary search's discarded ranges

Use the invariant: if the target occurs, at least one occurrence is inside the inclusive low–high range. Initially that range covers the whole list. If the middle value is too small, sorted order makes every value at or left of mid too small. Updating low to mid + 1 preserves every possible match. The update to high = mid - 1 follows the same reasoning for values that are too large.

On a match, the returned position directly meets the postcondition. If the range empties, the invariant rules out a target anywhere in the list. The input remains sorted because the search never changes it.

Show why execution stops

A shrinking nonnegative whole-number measure proves progress toward an end. In binary search, the number of candidate positions strictly decreases after every mismatch. The tested midpoint is excluded, so the loop cannot keep the same range forever. Bubble and selection sort make at most $n-1$ passes on nonempty input and no passes on empty input.

Merge sort reaches lists of zero or one items because every recursive call uses a shorter list. Those base cases are sorted. Assuming the shorter calls return correct sorted halves, merge repeatedly takes the smallest remaining item and preserves all items. This carries correctness back up to the original call.

Use tests for a different job

A test compares one actual result with one expected result. Passing many selected tests builds confidence, while a single failing valid input is a counterexample that disproves correctness. A general invariant argument covers the unbounded family of possible inputs that a finite collection of sample tests leaves unchecked. Testing is especially useful for checking whether actual code implements the method used in the argument.

An edge case is a valid input near a boundary where assumptions and loop limits are easy to get wrong. Plan the expected result from the specification before running the code. Otherwise a program's mistaken output can quietly become your expected answer.

Choose lists that exercise boundaries

Test empty, one-item, and two-item lists; already sorted and reversed lists; repeated and all-equal values; negative numbers; and odd and even lengths. For searches, include the first position, the last position, and targets absent below, above, and between stored values.

An empty binary search should return -1 without accessing an item: low = 0 and high = -1 make the initial range empty. Sorting [3, 3, 3] should return three copies of 3. An output of [3] would be ordered but would fail item preservation.

Trace the smallest failure

A binary search using while low < high fails to enter its loop for [5] with target 5. The fix is low <= high, since a one-position range still holds a candidate. This one-item test isolates the boundary more clearly than a long list does.

With low = mid, searching [10, 20] for 20 sets the midpoint to 0, sees 10, and leaves low at 0. The range is unchanged on the next repetition. Use low = mid + 1 to exclude a position already checked. A two-item list with the target last reveals this endless loop.

Bubble sort compares items[j] with items[j + 1]. On the first pass, the last valid left index is n - 2. Continuing to n - 1 reads beyond the list and raises Python's IndexError. Such a one-position boundary error is called an off-by-one error.

Check both output promises

For a sort, check adjacent order and the count of every original item. Use labeled records to test stability. Ana 85, Ben 92, Cara 85 must keep Ana before Cara when a stable score sort groups the equal scores. A score-only check would miss an exchange of those two records.

Generate random lists too. Compare their results with a trusted implementation such as Python's sorted. Keep duplicates and different lengths in the generated inputs. When a test fails, shrink the input while preserving the failure, then trace it by hand. Keep the small example as a regression test so the repaired bug stays detectable.

Keep midpoint arithmetic safe

Python integers grow as needed, so (low + high) // 2 does not overflow. Some languages use fixed-width integers. For very large nonnegative indexes, their sum can exceed the storable range. Java integer addition wraps; signed integer overflow in C has undefined behavior.

With valid indexes and low <= high, compute low + (high - low) // 2 instead. The difference is nonnegative, and the result stays between the endpoints. This calculates the same rounded-down midpoint without forming the potentially overflowing sum. Boundary testing and reasoning about the language's number representation work together here.

An algorithm fits a task when its requirements and costs match the data and the work being done. Consider input order, access to positions, number of future operations, extra memory, stability, and the cost of moving records.

Compare the methods

Binary search also needs sorted order and quick access to the middle. A good comparison includes those prerequisites; a small search count alone leaves out the cost of preparing unsuitable data.

Decide whether sorting first pays

For one search of a million unsorted items, linear search costs at most a million comparisons. Sorting first by merge sort costs about 20 million comparisons before the first binary search, which then needs at most 20 middle checks. Preparation overwhelms the saving on that one query.

For 100 queries on an unchanged list, repeated linear searches can cost 100 million comparisons. Sorting once and making 100 binary searches costs about 20 million comparisons plus 2,000 middle checks. The preparation is reused, making the second plan attractive. Under this rough cost model, break-even is around 20 searches. The estimate depends on comparable operation costs and worst-case scans; it is not a universal query threshold.

Weigh order, movement, and memory

Bubble sort can finish quickly when only a nearby pair is misplaced. [1, 2, 4, 3, 5] needs one swap in its first pass and a second pass to confirm order: seven comparisons. But “nearly sorted” does not guarantee few passes. A small value at the far right can move left only one position each pass.

Selection sort's few swaps help when records are expensive to move. Both selection and bubble sort use only a fixed amount of extra storage. Merge sort handles large lists with much slower time growth, but its usual list-based form needs room for about another list's worth of items.

If equal-key records must retain earlier ordering, choose a stable method. A list already alphabetical by name can be stably sorted by grade while staying alphabetical inside each grade group. Ordinary selection sort can disrupt those ties.

Use tested library tools

Real programs usually use the language's built-in sort. Python's stable sorting uses an adaptive merge-based method commonly called Timsort, benefiting from order already present in the input. sorted(items) returns a new list, while items.sort() changes the existing list. A method changing a list in place as an API behavior can still use temporary working memory internally; it need not satisfy the fixed-extra-storage definition used for the simple sorts above.

For a handful of items, simple, clear code may matter more than growth. For large collections, compare worst-case behavior and memory alongside the properties the task actually requires.