Search & Sort Algorithms

Algorithms in Detail

Searching Algorithms

A searching algorithm finds a specific item within a collection of data. You need to know two:

Linear Search

• Start at the first item in the list
• Compare it to the item you are looking for
• If it matches, you are done
• If not, move to the next item
• Repeat until you find it or reach the end of the list

INPUT searchItem
FOR i = 0 TO LENGTH(list) - 1
    IF list[i] == searchItem THEN
        OUTPUT "Found at position " + i
        STOP
    ENDIF
ENDFOR
OUTPUT "Item not found"

Pros: Works on any list (sorted or unsorted). Simple to understand and implement.

Cons: Slow for large lists — in the worst case, you check every single item.

Binary Search

Binary search is much faster, but the list must be sorted first. It works by repeatedly halving the data:

• The list must be sorted first
• Look at the middle item
• If it matches, you are done
• If your target is smaller, discard the right half
• If your target is larger, discard the left half
• Repeat on the remaining half until found or nothing left

INPUT searchItem
SET low TO 0
SET high TO LENGTH(list) - 1
WHILE low <= high
    SET mid TO (low + high) DIV 2
    IF list[mid] == searchItem THEN
        OUTPUT "Found at position " + mid
        STOP
    ELSEIF list[mid] < searchItem THEN
        SET low TO mid + 1
    ELSE
        SET high TO mid - 1
    ENDIF
ENDWHILE
OUTPUT "Item not found"

Pros: Very fast, even with huge lists. Each step eliminates half the remaining data.

Cons: Only works on sorted data. Slightly more complex to implement.

Sorting Algorithms

Sorting means arranging data into a particular order (usually ascending or descending). You need to know these sorting algorithms:

Bubble Sort

• Compare each pair of adjacent items
• If they are in the wrong order, swap them
• Repeat the entire pass through the list
• Stop when a complete pass is made with no swaps

REPEAT
    SET swapped TO FALSE
    FOR i = 0 TO LENGTH(list) - 2
        IF list[i] > list[i + 1] THEN
            SWAP list[i] AND list[i + 1]
            SET swapped TO TRUE
        ENDIF
    ENDFOR
UNTIL swapped == FALSE

Example walkthrough: Sorting [5, 3, 8, 1]

Pros: Simple to understand and code. Detects if the list is already sorted (no swaps = stop early).

Cons: Very slow for large lists. Makes many unnecessary comparisons.

Insertion Sort

Think about how you sort a hand of playing cards. You pick up one card at a time and slide it into the correct position among the cards you have already sorted.

• Start with the second item in the list (the first item is already “sorted” by itself)
• Compare it with items to its left
• Shift larger items one place to the right to make room
• Insert the current item into its correct position
• Repeat for every remaining item in the list

FOR i = 1 TO LENGTH(list) - 1
    SET current TO list[i]
    SET j TO i - 1
    WHILE j >= 0 AND list[j] > current
        SET list[j + 1] TO list[j]
        SET j TO j - 1
    ENDWHILE
    SET list[j + 1] TO current
ENDFOR

Example walkthrough: Sorting [5, 3, 8, 1]

Pros: Simple to understand. Very efficient for small lists or lists that are already nearly sorted. Uses very little extra memory.

Cons: Slow for large, unsorted lists (similar to bubble sort).

Merge Sort

Merge sort uses a “divide and conquer” approach. Instead of sorting the whole list at once, you split it in half, then split those halves in half again, and keep going until you have sub-lists of just one item each (which are already “sorted”). Then you merge them back together in the right order.

• Divide: Split the list in half, repeatedly, until each sub-list has just one item
• Conquer: Merge pairs of sub-lists back together in sorted order
• Keep merging until you have one fully sorted list

FUNCTION mergeSort(list)
    IF LENGTH(list) <= 1 THEN
        RETURN list
    ENDIF
    SET mid TO LENGTH(list) DIV 2
    SET left TO mergeSort(list[0 TO mid - 1])
    SET right TO mergeSort(list[mid TO end])
    RETURN merge(left, right)
ENDFUNCTION

FUNCTION merge(left, right)
    SET result TO empty list
    WHILE left is not empty AND right is not empty
        IF left[0] <= right[0] THEN
            APPEND left[0] TO result
            REMOVE first item from left
        ELSE
            APPEND right[0] TO result
            REMOVE first item from right
        ENDIF
    ENDWHILE
    APPEND remaining items to result
    RETURN result
ENDFUNCTION

Example walkthrough: Sorting [6, 3, 8, 1]

Pros: Much faster than bubble sort for large lists. Consistent performance regardless of how the data starts.

Cons: Uses more memory (needs extra space for the sub-lists). More complex to code.

Comparing Algorithms: When to Use Which

How Many Comparisons?

To understand why some algorithms are faster than others, think about how many comparisons they need for a list of 1,000 items:

The choice of algorithm makes an enormous difference. For large data sets, a slow algorithm can take hundreds of times longer than a fast one to produce the same result.

Key Vocabulary

Make sure you understand and can define all of these terms.

Past Paper Questions

Try these exam-style questions, then click to reveal the mark scheme answer.