A search algorithm locates a target value within a collection of data. The efficiency of a search algorithm is measured by the number of comparisons required to find (or confirm the absence of) the target element.

1.1 Linear Search

Design: Linear search (also called sequential search) examines each element in the list one by one, starting from the first element, until either the target is found or the entire list has been checked. It works on both sorted and unsorted lists.

Algorithm:

1. Start from the first element
2. Compare the current element with the target
3. If they match, return the position
4. If they do not match, move to the next element
5. Repeat steps 2–4 until the element is found or the list ends
6. If the list ends without finding the target, report that the element is not present

Performance: The time complexity of linear search is O(n) in the worst case, where n is the number of elements. In the best case, the element is found at the first position with O(1) time. On average, approximately n/2 comparisons are needed.

Example: Consider searching for the number 30 in the list: 15, 22, 10, 45, 30, 50

• Compare 30 with 15 → not equal → move to next
• Compare 30 with 22 → not equal → move to next
• Compare 30 with 10 → not equal → move to next
• Compare 30 with 45 → not equal → move to next
• Compare 30 with 30 → equal → found at position 5

Advantages:

• Simple to implement
• Works on unsorted data
• Fast for small datasets

Disadvantages:

• Slow for large datasets (requires up to n comparisons)
• Inefficient compared to other methods for large lists

1.2 Binary Search

Design: Binary search efficiently finds an element in a sorted list by repeatedly dividing the search interval in half. This is called the "divide and conquer" approach. The algorithm compares the target with the middle element; if they are not equal, it eliminates the half where the target cannot exist and continues searching in the remaining half.

Important: Binary search requires the list to be sorted in ascending or descending order.

Algorithm:

1. Let low be the first index and high be the last index of the list
2. Calculate mid = (low + high) / 2
3. If the middle element equals the target, return the position
4. If the target is less than the middle element, set high = mid - 1 and repeat from step 2
5. If the target is greater than the middle element, set low = mid + 1 and repeat from step 2
6. If low > high, the element is not in the list

Performance: Binary search has a time complexity of O(log n) because the search space is halved with each comparison. This is significantly faster than linear search for large datasets.

Example: Search for 56 in the sorted array: 10, 12, 24, 29, 37, 40, 51, 56, 68

• Step 1: low = 0, high = 8, mid = 4, a[4] = 37
  • 56 > 37, so search the upper half: low = 5
• Step 2: low = 5, high = 8, mid = 6, a[6] = 51
  • 56 > 51, so search the upper half: low = 7
• Step 3: low = 7, high = 8, mid = 7, a[7] = 56
  • 56 = 56, found at position 7

This required only 3 comparisons instead of 8 for linear search.

Advantages:

• Much faster than linear search for large sorted datasets
• Time complexity of O(log n) is highly efficient

Disadvantages:

• Requires sorted data (preprocessing may be needed)
• More complex to implement than linear search

A sorting algorithm arranges elements in a specific order (ascending or descending). The efficiency of sorting algorithms is measured by the number of comparisons and swaps required, typically expressed as time complexity.

2.1 Selection Sort

Design: Selection sort divides the list into two portions: sorted and unsorted. It repeatedly selects the smallest (or largest) element from the unsorted portion and places it at the beginning of the sorted portion.

Algorithm:

1. Start from the first position
2. Find the minimum element in the unsorted portion
3. Swap the minimum element with the first element of the unsorted portion
4. Move the boundary between sorted and unsorted portions one step forward
5. Repeat steps 2–4 until the entire list is sorted

Performance: Selection sort has a time complexity of O(n²) regardless of the initial order of data. It always performs approximately n(n-1)/2 comparisons.

Example: Sort [64, 25, 12, 22, 11] in ascending order:

• Pass 1: Find minimum (11), swap with 64 → [11, 25, 12, 22, 64]
• Pass 2: Find minimum in remaining (12), swap with 25 → [11, 12, 25, 22, 64]
• Pass 3: Find minimum in remaining (22), swap with 25 → [11, 12, 22, 25, 64]
• Pass 4: Only one element remaining → already sorted

Advantages:

• Simple to understand and implement
• Performs well for small datasets
• In-place sorting (no extra memory needed)

Disadvantages:

• Inefficient for large datasets (O(n²) time complexity)
• Does not adapt to existing order

2.2 Insertion Sort

Design: Insertion sort builds the sorted array one element at a time by taking each element and inserting it into its correct position within the already-sorted portion. It is similar to how playing cards are sorted in hand.

Algorithm:

1. Consider the first element as a sorted sublist
2. For each element in the unsorted portion (starting from the second):
   • Store the current element in a temporary variable
   • Compare it with elements in the sorted portion
   • Shift elements that are greater than the current element one position to the right
   • Insert the current element into its correct position

Performance: Insertion sort has O(n²) time complexity in the worst and average cases, but O(n) in the best case (when the list is already sorted).

Example: Sort [5, 2, 4, 6, 1, 3] in ascending order:

• Start: [5 | 2, 4, 6, 1, 3] (left is sorted)
• Insert 2: Compare with 5, shift 5 right, insert 2 → [2, 5 | 4, 6, 1, 3]
• Insert 4: Compare with 5, shift 5 right, insert 4 → [2, 4, 5 | 6, 1, 3]
• Continue similarly until sorted: [1, 2, 3, 4, 5, 6]

Advantages:

• Efficient for small or nearly sorted datasets
• Stable (maintains order of equal elements)
• In-place and simple to implement

Disadvantages:

• Inefficient for large unsorted datasets
• Many shifts required for reverse-sorted data

2.3 Bubble Sort

Design: Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position, like air bubbles rising in water.

Algorithm:

1. Repeat n-1 times (where n is the number of elements):
   • For each pair of adjacent elements:
     • If they are in the wrong order, swap them
2. If no swaps occur in a pass, the list is already sorted (optimization)

Performance: Bubble sort has O(n²) time complexity in the worst and average cases. With optimization (early exit when no swaps occur), best case is O(n) for already sorted data.

Example: Sort [5, 1, 12, 6, 23] in ascending order:

• Pass 1: [5, 1, 12, 6, 23] → compare 5,1 → swap → [1, 5, 12, 6, 23]
  • Compare 5,12 → no swap → [1, 5, 12, 6, 23]
  • Compare 12,6 → swap → [1, 5, 6, 12, 23]
  • Compare 12,23 → no swap → [1, 5, 6, 12, 23]
• Pass 2: [1, 5, 6, 12, 23] → already sorted after two more comparisons

Advantages:

• Simple to understand and implement
• Can detect if list is already sorted (with optimization)
• Stable sorting algorithm

Disadvantages:

• Very slow for large datasets
• Many unnecessary comparisons and swaps even when nearly sorted

2.4 Heap Sort

Design: Heap sort uses a binary heap data structure to sort elements. It first builds a max-heap (or min-heap) where the root contains the maximum (or minimum) element, then repeatedly extracts the root and heapifies the remaining elements.

Algorithm:

1. Build a max-heap from the unsorted array
2. Repeat until the heap is empty:
   • Swap the root (maximum element) with the last element
   • Reduce the heap size by 1
   • Heapify the root to maintain the heap property

Performance: Heap sort has a consistent time complexity of O(n log n) in all cases (best, worst, and average).

Example: Sort [11, 9, 6, 13, 2, 8] in ascending order:

• Build max-heap: [13, 11, 8, 9, 2, 6]
• Extract 13, heapify: [11, 9, 8, 6, 2 | 13]
• Extract 11, heapify: [9, 6, 8, 2 | 11, 13]
• Continue until sorted: [2, 6, 8, 9, 11, 13]

Advantages:

• Consistent O(n log n) performance regardless of input
• In-place sorting (O(1) extra space)
• Suitable for large datasets

Disadvantages:

• Not stable (may change relative order of equal elements)
• More complex to implement than simpler algorithms
• Less cache-friendly than Quick Sort

2.5 Quick Sort

Design: Quick sort is a divide-and-conquer algorithm that selects a "pivot" element and partitions the array around the pivot so that elements less than the pivot are on the left and elements greater than the pivot are on the right. It then recursively sorts the sub-arrays.

Algorithm:

1. Select a pivot element (commonly the last element or middle element)
2. Partition the array:
   • Move all elements smaller than the pivot to the left
   • Move all elements greater than the pivot to the right
3. Place the pivot in its correct sorted position
4. Recursively apply steps 1–3 to the left and right sub-arrays

Performance: Quick sort has O(n log n) average-case complexity but O(n²) worst-case complexity (when the pivot is always the smallest or largest element).

Example: Sort [28, 12, 5, 20, 17, 30, 9] using 28 as pivot:

• Partition: Move elements < 28 to left, > 28 to right
• After first partition: [12, 5, 20, 17, 9, 28, 30]
• Recursively sort left portion [12, 5, 20, 17, 9] and right portion [30]

Advantages:

• Very fast in practice for average cases
• In-place sorting (low memory overhead)
• Divide-and-conquer allows parallel processing

Disadvantages:

• Worst-case O(n²) for sorted or reverse-sorted data
• Not stable
• Recursive calls require stack space

2.6 Merge Sort

Design: Merge sort is a divide-and-conquer algorithm that divides the array into two halves, recursively sorts each half, and then merges the two sorted halves back together. It works by merging smaller sorted lists into larger sorted lists.

Algorithm:

1. If the array has more than one element:
   • Divide the array into two roughly equal halves
   • Recursively sort each half
   • Merge the two sorted halves into one sorted array
2. The merge process compares elements from both halves and places the smaller element in the result array

Performance: Merge sort has a consistent time complexity of O(n log n) in all cases.

Example: Sort [32, 15, 7, 20, 5, 18]:

• Split: [32, 15, 7] and [20, 5, 18]
• Split further: [32, 15], [7] and [20, 5], [18]
• Split to single elements: [32], [15], [7], [20], [5], [18]
• Merge: [15, 32], [5, 7, 18, 20]
• Final merge: [5, 7, 15, 18, 20, 32]

Advantages:

• Consistent O(n log n) performance
• Stable sorting algorithm
• Works well for linked lists and external sorting (files)

Disadvantages:

• Requires O(n) extra space for merging
• Slower than Quick Sort for small datasets in practice
• Less cache-friendly due to array splitting

Stability means that equal elements maintain their relative order after sorting.

When selecting a sorting algorithm, consider:

• Data size: For small datasets, insertion sort or bubble sort may be sufficient
• Initial order: If nearly sorted, insertion sort or bubble sort with optimization perform well
• Stability requirement: Use stable algorithms (merge sort, insertion sort, bubble sort) when relative order of equal elements matters
• Memory constraints: In-place algorithms (selection, insertion, bubble, heap, quick sort) use less memory
• Consistency needed: Heap sort and merge sort guarantee O(n log n) in all cases

In Tanzania, searching and sorting algorithms are used in mobile banking systems like M-Pesa or banking apps. When a customer searches for a transaction in their transaction history (which may contain thousands of records), binary search quickly locates the specific transaction if the list is sorted by date. Similarly, when a shopkeeper at a local market in Dar es Salaam arranges inventory items or generates sales reports sorted by product name or price, sorting algorithms ensure the data is organised efficiently for quick lookup and decision-making.