Computer Science · College · BCA, BTech & MCA

Searching & Sorting Algorithms: Binary Search, QuickSort & MergeSort

Comprehensive guide to sorting and searching: Linear vs Binary Search, Bubble, Insertion, QuickSort (Divide and Conquer) and MergeSort, with Big-O space and time complexity comparisons.

1Searching Algorithms: Linear vs Binary Search

Searching & Sorting Algorithms: Binary Search, QuickSort & MergeSort: Subject, Target Audience, Topic Core Full size

Searching & Sorting Algorithms: Binary Search, QuickSort & MergeSort

Comprehensive guide to sorting and searching: Linear vs Binary Search, Bubble, Insertion, QuickSort (Divide and Conquer) and MergeSort, with Big-O space and time complexity comparisons.

  1. 1Subject — Computer Science
  2. 2Target Audience — BCA, BTech & MCA Students
  3. 3Topic Core — Divide & Conquer, Big-O Matrix & Stability

Linear Searchsequentially tests every element in an array until a target match is found, executing in O(n)O(n) time on unsorted collections.Binary Searchoperates onsorted arraysby repeatedly halving the search search space, achieving O(log⁡n)O(\log n) logarithmic runtime.

Binary Search Recurrence Relation

T(n)=T(n/2)+O(1)  ⟹  T(n)=O(log⁡2n)T(n) = T(n/2) + O(1) \implies T(n) = O(\log_2 n)
  • n = Number of elements in the sorted array
  • T(n) = Time complexity to search an array of size n
python· Iterative Binary Search with Overflow-Safe Midpoint
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        # Avoid integer overflow: low + (high - low) // 2
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            return mid # Target found at index mid
        elif arr[mid] < target:
            low = mid + 1 # Search right half
        else:
            high = mid - 1 # Search left half
            
    return -1 # Not found

# Example
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("Index of 23:", binary_search(data, 23))
Output:
Index of 23: 5

2Divide & Conquer: Merge Sort vs Quick Sort

Merge Sortdivides an array into two halves, recursively sorts both, and then merges the sorted halves in O(n)O(n) time. It guaranteesO(nlog⁡n)O(n \log n) time in all casesand isstable, but requires O(n)O(n) auxiliary memory.

Quick Sortselects apivot elementand partitions the array such that all smaller elements reside on the left and larger on the right. It operatesin-place(O(log⁡n)O(\log n) auxiliary stack memory) and runs in average O(nlog⁡n)O(n \log n), but degrades to O(n2)O(n^2) when the pivot is poorly chosen.

Merge Sort Execution Pipeline

  1. 1

    Divide

    Compute mid = low + (high - low) / 2 and split array into left and right sub-arrays

  2. 2

    Conquer

    Recursively invoke mergeSort(left) and mergeSort(right) until base size 1 is reached

  3. 3

    Combine / Merge

    Merge the two sorted arrays into a single sorted array using two pointer comparisons in O(n)

3Algorithmic Complexity & Stability Master Table

Sorting Algorithms Master Benchmark Matrix

  • Bubble Sort

    Best Time
    O(n) (optimized)
    Average Time
    O(n²)
    Worst Time
    O(n²)
    Worst Space
    O(1)
    Stable?
    Yes

  • Selection Sort

    Best Time
    O(n²)
    Average Time
    O(n²)
    Worst Time
    O(n²)
    Worst Space
    O(1)
    Stable?
    No

  • Insertion Sort

    Best Time
    O(n)
    Average Time
    O(n²)
    Worst Time
    O(n²)
    Worst Space
    O(1)
    Stable?
    Yes

  • Merge Sort

    Best Time
    O(n log n)
    Average Time
    O(n log n)
    Worst Time
    O(n log n)
    Worst Space
    O(n)
    Stable?
    Yes

  • Quick Sort

    Best Time
    O(n log n)
    Average Time
    O(n log n)
    Worst Time
    O(n²)
    Worst Space
    O(log n)
    Stable?
    No

  • Heap Sort

    Best Time
    O(n log n)
    Average Time
    O(n log n)
    Worst Time
    O(n log n)
    Worst Space
    O(1)
    Stable?
    No

Definition

Algorithm Stability — A sorting algorithm is stable if two elements with equal keys appear in the sorted output in the exact same relative order as they were in the unsorted input.

Remember

  • Binary Search requires a sorted array and executes in O(log n) time by halving search intervals.
  • Merge Sort guarantees O(n log n) in best, average, and worst cases, and is stable, but requires O(n) auxiliary space.
  • Quick Sort sorts in-place with O(n log n) average time, making it the fastest general-purpose internal sort in practice.
  • Insertion Sort is exceptionally fast O(n) for small or nearly sorted collections and forms the basis of TimSort.

Check yourself

  1. Question 1

    Which sorting algorithm has a worst-case time complexity of O(n log n) and requires O(1) auxiliary space?

  2. Question 2

    Why is mid =low +(high −low )/2\text{mid}\ = \text{low}\ + (\text{high}\ - \text{low}\ ) / 2 preferred over mid =(low +high )/2\text{mid}\ = (\text{low}\ + \text{high}\ ) / 2 in Binary Search?

Read it? Now test it. Timed exam questions on this topic, then a report on what to revise.

Take a test

Want a lesson on another topic? Type any topic or add a photo of your notes — get a lesson like this in seconds.

Learn a topic

More Computer Science explained