Computer Science•45 min read

Searching & Sorting Algorithms: Complete Guide with Code in 5 Languages

Master Linear Search, Binary Search, Bubble Sort, Merge Sort, Quick Sort & more. Code in Python, Java, C++, JavaScript, C.

Dev Kant Kumar
Dev Kant Kumar
February 9, 2026

30-Second Key Takeaways

TL;DR

Quick digest before you dive deep

Master Linear Search, Binary Search, Bubble Sort, Merge Sort, Quick Sort & more. Code in Python, Java, C++, JavaScript, C.
Comprehensive guide to searching and sorting algorithms with implementations in Python, Java, C++, JavaScript, and C.
Perfect for coding interviews, DSA preparation, and computer science students.
Complete DSA Guide 2026

Searching & Sorting
Algorithms Explained

Master the fundamental algorithms that power everything from database queries to Google search. Complete with code in Python, Java, C++, JavaScript, and C.

45-60 min read
15+ Algorithms
5 Languages
Searching and Sorting Algorithms Complete Guide 2026

Imagine you're in a library with a million books, and you need to find a specific one. Would you check every single book from the first shelf? Or would you use a smarter approach-perhaps starting from the middle and eliminating half the options with each step?

This is the essence of searching and sorting algorithms-the backbone of computer science and the foundation of every software system you interact with daily. From the autocomplete in your search bar to the way your social media feed is organized, these algorithms are working silently behind the scenes.

Why These Algorithms Matter

Understanding searching and sorting isn't just about passing coding interviews (though it absolutely helps there). It's about developing the algorithmic thinking that separates average developers from exceptional ones. When you understand why binary search is O(log n) or why QuickSort beats BubbleSort in practice, you'll start seeing optimization opportunities everywhere.

Searching Algorithms

Finding specific data in a collection. Used in databases, file systems, and virtually every application that retrieves information.

Sorting Algorithms

Organizing data in a specific order. Critical for efficient searching, data analysis, and presenting information to users.

What You'll Learn

This comprehensive guide covers everything you need to master searching and sorting:

  • •Algorithm Complexity Analysis - Understanding Big O notation and how to evaluate algorithm efficiency
  • •Searching Algorithms - Linear Search, Binary Search, Jump Search, and Interpolation Search
  • •Simple Sorting Algorithms - Bubble Sort, Selection Sort, and Insertion Sort
  • •Advanced Sorting Algorithms - Merge Sort, Quick Sort, and Heap Sort
  • •Non-Comparison Sorts - Counting Sort and Radix Sort
  • •Practical Applications - Real-world use cases and interview patterns

How to Use This Guide

Each algorithm includes a visual explanation, pseudocode, implementations in 5 programming languages (Python, Java, C++, JavaScript, C), complexity analysis, and practical use cases.

Whether you're a beginner learning DSA or preparing for FAANG interviews, this guide has you covered.

Real-World Applications

Every time you use a computer or smartphone, you're benefiting from these algorithms:

Search Engines

Binary search on indexed data

Social Media

Sorting feeds by relevance

E-Commerce

Product sorting & filtering

Databases

B-tree search & indexing

Gaming

Collision detection sorting

Data Analytics

Sorting for visualization

Interview Tip

Sorting and searching questions appear in over 60% of technical interviews. Mastering these fundamentals gives you a significant edge over other candidates. Companies like Google, Amazon, and Microsoft frequently test these concepts.

1

Understanding Algorithm Complexity

Big O Notation & Analysis

Before diving into specific algorithms, you need to understand how we measure algorithm efficiency. This is crucial for choosing the right algorithm and for technical interviews where complexity analysis is expected.

Time Complexity (Big O Notation)

Time complexity describes how the runtime of an algorithm grows as the input size increases. We use Big O notation to express the worst-case scenario, giving us an upper bound on the algorithm's performance.

Why Big O?

Big O notation ignores constants and lower-order terms because they become insignificant as input grows. An O(n) algorithm with a large constant is still better than O(n²) for large inputs.
NotationNameExamplen=100n=10,000
O(1)ConstantArray access, hash lookup11
O(log n)LogarithmicBinary search~7~13
O(n)LinearLinear search, single loop10010,000
O(n log n)LinearithmicMerge sort, Quick sort~664~132,877
O(n²)QuadraticBubble sort, nested loops10,000100,000,000
O(2ⁿ)ExponentialRecursive Fibonacci (naive)2¹⁰⁰ ⚠️∞

Growth Rate Comparison

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(2ⁿ)
🚀 Fast
🐌 Slow

Space Complexity

Space complexity measures how much additional memory an algorithm needs relative to its input size. This is crucial when working with limited memory or large datasets.

In-Place Algorithms (O(1))

Modify input directly without using extra space proportional to input.

  • ✅ Bubble Sort
  • ✅ Selection Sort
  • ✅ Insertion Sort
  • ✅ Quick Sort
  • ✅ Heap Sort

Out-of-Place Algorithms

Require additional memory for temporary storage.

  • ⚠️ Merge Sort - O(n)
  • ⚠️ Counting Sort - O(k)
  • ⚠️ Radix Sort - O(n + k)
  • ⚠️ Bucket Sort - O(n)

Best, Average, and Worst Cases

Algorithms can perform differently depending on the input:

CaseDescriptionExample
Best CaseMost favorable inputBinary search finds target at first comparison
Average CaseExpected performance on random inputTarget found after ~log n comparisons
Worst CaseMost unfavorable inputQuickSort on already sorted array (poor pivot)

Interview Alert

When asked about time complexity, always clarify: "Are you asking about best, average, or worst case?" Most interviewers expect the worst case unless specified otherwise.

How to Analyze Algorithm Complexity

  1. 1
    Count the basic operations

    Identify operations like comparisons, assignments, and arithmetic.

  2. 2
    Look at loops

    Single loop over n elements → O(n), Nested loops → O(n²)

  3. 3
    Consider recursion

    Use recurrence relations (T(n) = 2T(n/2) + O(n) for Merge Sort)

  4. 4
    Drop constants and lower-order terms

    O(3n² + 5n + 10) simplifies to O(n²)

Key Takeaway

Understanding complexity is essential for choosing the right algorithm. A difference between O(n) and O(n²) can mean the difference between an algorithm that runs in seconds vs. one that takes hours on large inputs. In interviews, always discuss complexity tradeoffs when proposing solutions.

2
The Simplest Search Algorithm

Linear Search is the simplest searching algorithm. It sequentially checks each element of the list until a match is found or the entire list has been searched.

How Linear Search Works

Think of Linear Search like looking for a specific card in a shuffled deck. You start from the first card and check each one until you find the card you're looking for (or reach the end).

🔍 Step-by-Step Example: Finding 22 in [64, 34, 25, 12, 22, 11, 90]

Step 1Compare 64 → 64 ≠ 22, move to next
Step 2Compare 34 → 34 ≠ 22, move to next
Step 3Compare 25 → 25 ≠ 22, move to next
Step 4Compare 12 → 12 ≠ 22, move to next
Step 5Compare 22 → 22 = 22, FOUND at index 4! ✅
Linear Search Algorithm
FUNCTION LinearSearch(array, target):
    FOR i = 0 TO array.length - 1:
        IF array[i] == target:
            RETURN i        // Element found
    END FOR
    RETURN -1              // Element not found
END FUNCTION

Code Implementation (5 Languages)

1# Linear Search in Python
2# Time: O(n) | Space: O(1)
3
4def linear_search(arr, target):
5 """
6 Search for target in array sequentially.
7 Returns index if found, -1 otherwise.
8 """
9 for i in range(len(arr)):
10 if arr[i] == target:
11 return i # Found! Return index
12 return -1 # Not found
13
14# Example usage
15arr = [64, 34, 25, 12, 22, 11, 90]
16target = 22
17
18result = linear_search(arr, target)
19if result != -1:
20 print(f"Element found at index {result}")
21else:
22 print("Element not found")
23
24# Output: Element found at index 4
UTF-8Ln 24, Col 0

Complexity Analysis

MetricValue
Best CaseO(1)
Average CaseO(n)
Worst CaseO(n)
SpaceO(1)
Stable?✅ Yes
In-Place?✅ Yes

Complexity Explanation

  • Best Case O(1): Target is at the first position
  • Average Case O(n): Target is somewhere in the middle, need to check ~n/2 elements
  • Worst Case O(n): Target is at the last position or not present
  • Space O(1): Only uses a few variables, no extra space proportional to input

✅ Use Linear Search When:

  • • Array is unsorted
  • • Array is small (n < 100)
  • • Searching only once
  • • Data is stored in linked list
  • • Simplicity is more important than speed

❌ Avoid Linear Search When:

  • • Array is sorted (use Binary Search)
  • • Array is large (n > 1000)
  • • Need to search multiple times
  • • Performance is critical
  • • Have access to hash tables

Advantages & Disadvantages

AdvantagesDisadvantages
Simple to implementSlow for large datasets
Works on unsorted arraysO(n) time complexity
No preprocessing requiredNot suitable for frequent searches
Works on linked listsLess efficient than binary search on sorted data

Key Takeaway

Linear Search is your go-to algorithm for small or unsorted data. It's the baseline that every other search algorithm improves upon. While it's not efficient for large datasets, its simplicity makes it valuable for quick prototypes and situations where simplicity trumps performance.

3
The Most Important Search Algorithm

Binary Search is the most important searching algorithm you'll ever learn. It reduces search time from O(n) to O(log n) by repeatedly dividing the search space in half-a concept called divide and conquer.

Critical Prerequisite

Binary Search only works on sorted arrays. If your data is unsorted, you must sort it first (O(n log n)) or use Linear Search. However, if you're searching multiple times, the cost of sorting once is worth it.

How Binary Search Works

Imagine you're looking for a word in a dictionary. You don't start from page 1-you open to the middle, see if your word comes before or after, and eliminate half the pages with each step. That's binary search!

🔍 Visual Walkthrough: Finding 25 in [11, 12, 22, 25, 34, 64, 90]

Step 1left=0, right=6, mid=3
11
12
22
25
34
64
90

arr[3] = 25 = target → FOUND! ✅

Another Example: Finding 12
Step 1mid=3 → arr[3]=25 > 12 → Search LEFT half [0..2]
Step 2mid=1 → arr[1]=12 = target → FOUND!

Only 2 comparisons instead of 7 with linear search!

Binary Search Algorithm
FUNCTION BinarySearch(array, target):
    left = 0
    right = array.length - 1

    WHILE left <= right:
        mid = left + (right - left) / 2    // Avoid overflow

        IF array[mid] == target:
            RETURN mid                      // Found!
        ELSE IF array[mid] < target:
            left = mid + 1                  // Search right half
        ELSE:
            right = mid - 1                 // Search left half
    END WHILE

    RETURN -1                              // Not found
END FUNCTION

Iterative Implementation (Preferred)

The iterative approach is generally preferred because it uses O(1) space and avoids the overhead of recursive function calls.

1# Binary Search (Iterative) in Python
2# Time: O(log n) | Space: O(1)
3
4def binary_search(arr, target):
5 """
6 Search for target in SORTED array using divide and conquer.
7 Returns index if found, -1 otherwise.
8 """
9 left = 0
10 right = len(arr) - 1
11
12 while left <= right:
13 # Calculate middle index (avoids overflow)
14 mid = left + (right - left) // 2
15
16 if arr[mid] == target:
17 return mid # Found! Return index
18 elif arr[mid] < target:
19 left = mid + 1 # Target is in right half
20 else:
21 right = mid - 1 # Target is in left half
22
23 return -1 # Not found
24
25# Example usage
26arr = [11, 12, 22, 25, 34, 64, 90] # Must be sorted!
27target = 25
28
29result = binary_search(arr, target)
30print(f"Element found at index {result}") # Output: 3
UTF-8Ln 30, Col 0

Recursive Implementation

The recursive approach is more elegant and mirrors the divide-and-conquer concept, but uses O(log n) space for the call stack.

1# Binary Search (Recursive) in Python
2# Time: O(log n) | Space: O(log n) - due to call stack
3
4def binary_search_recursive(arr, target, left, right):
5 """
6 Recursive binary search implementation.
7 """
8 # Base case: element not found
9 if left > right:
10 return -1
11
12 mid = left + (right - left) // 2
13
14 if arr[mid] == target:
15 return mid # Found!
16 elif arr[mid] < target:
17 return binary_search_recursive(arr, target, mid + 1, right)
18 else:
19 return binary_search_recursive(arr, target, left, mid - 1)
20
21# Helper function for cleaner API
22def binary_search(arr, target):
23 return binary_search_recursive(arr, target, 0, len(arr) - 1)
24
25# Example usage
26arr = [11, 12, 22, 25, 34, 64, 90]
27print(f"Found at index: {binary_search(arr, 25)}")
UTF-8Ln 27, Col 0

Complexity Analysis

MetricValue
Best CaseO(1)
Average CaseO(log n)
Worst CaseO(log n)
SpaceO(1) iterative / O(log n) recursive

🧮 Why O(log n)? The Math Explained

Each iteration divides the search space in half:

n → n/2 → n/4 → n/8 → ... → 1

After k steps: n/2^k = 1 → k = log₂(n)

100
elements
~7 steps
1,000
elements
~10 steps
1M
elements
~20 steps

Common Mistakes & Edge Cases

Integer Overflow Bug

mid = (left + right) / 2 can overflow!

✅ Fix: mid = left + (right - left) / 2

Infinite Loop

Wrong: while (left < right) - misses edge case

✅ Fix: while (left <= right)

Off-by-One Error

Wrong: left = mid or right = mid

✅ Fix: left = mid + 1 and right = mid - 1

Edge Cases to Handle

  • • Empty array - return -1
  • • Single element - check if it matches
  • • Target smaller than all elements - return -1
  • • Target larger than all elements - return -1
  • • Duplicate elements - returns any matching index (variations exist for first/last)

Binary Search Variations

Lower Bound

Find first element ≥ target

Upper Bound

Find first element > target

First Occurrence

Find leftmost matching index

Last Occurrence

Find rightmost matching index

Search in Rotated Array

Modified binary search for rotated sorted arrays

Peak Element

Find local maximum in array

Real-World Applications

Dictionary Lookup

Finding words in sorted dictionaries

Search Engines

Searching indexed, sorted data

Database Indexing

B-tree searches are based on binary search

Version Control

Git bisect uses binary search to find bugs

Game Development

Collision detection & pathfinding

Autocomplete

Prefix matching in sorted lists

Key Takeaway

Binary Search is the gold standard for searching sorted data. Its O(log n) complexity makes it incredibly efficient-searching through a billion elements takes only about 30 comparisons! Master both iterative and recursive implementations, as interviewers love testing edge cases and variations.

4

Bubble Sort

Simple but Slow

Bubble Sort is the simplest sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order-like bubbles rising to the surface.

How Bubble Sort Works

Imagine bubbles in a glass of soda-heavier elements "sink" to the bottom while lighter ones "bubble up" to the top with each pass through the array.

🫧 Visual Walkthrough: Sorting [64, 34, 25, 12]

Pass 1:[64, 34, 25, 12] → [34, 64, 25, 12] → [34, 25, 64, 12] → [34, 25, 12, 64]
Pass 2:[34, 25, 12, 64] → [25, 34, 12, 64] → [25, 12, 34, 64]
Pass 3:[25, 12, 34, 64] → [12, 25, 34, 64] ✅
Bubble Sort Algorithm
FUNCTION BubbleSort(array):
    n = array.length

    FOR i = 0 TO n-1:
        swapped = false

        FOR j = 0 TO n-i-2:
            IF array[j] > array[j+1]:
                SWAP(array[j], array[j+1])
                swapped = true

        IF NOT swapped:    // Optimization
            BREAK          // Already sorted

    RETURN array
END FUNCTION

Code Implementation (5 Languages)

1# Bubble Sort in Python
2# Time: O(n²) | Space: O(1)
3
4def bubble_sort(arr):
5 """
6 Sort array by repeatedly swapping adjacent elements.
7 """
8 n = len(arr)
9
10 for i in range(n):
11 # Track if any swap happened
12 swapped = False
13
14 # Last i elements are already sorted
15 for j in range(0, n - i - 1):
16 # Compare adjacent elements
17 if arr[j] > arr[j + 1]:
18 # Swap them
19 arr[j], arr[j + 1] = arr[j + 1], arr[j]
20 swapped = True
21
22 # Optimization: if no swaps, array is sorted
23 if not swapped:
24 break
25
26 return arr
27
28# Example
29arr = [64, 34, 25, 12, 22, 11, 90]
30print("Sorted:", bubble_sort(arr))
31# Output: [11, 12, 22, 25, 34, 64, 90]
UTF-8Ln 31, Col 0

Complexity Analysis

MetricValue
Best CaseO(n)
Average CaseO(n²)
Worst CaseO(n²)
SpaceO(1)
Stable?✅ Yes
In-Place?✅ Yes

Why O(n) Best Case?

With the swapped optimization, if the array is already sorted, we detect it in one pass and exit early-making it O(n) in the best case.

When to Use Bubble Sort

✅ Good For:

  • • Educational purposes
  • • Very small arrays (n < 20)
  • • Nearly sorted data
  • • Checking if array is sorted

❌ Avoid For:

  • • Large datasets
  • • Production code (usually)
  • • Performance-critical applications
  • • Any serious sorting needs

Key Takeaway

Bubble Sort is mainly used for educational purposes to understand sorting concepts. In practice, use more efficient algorithms like Quick Sort or Merge Sort. However, knowing Bubble Sort is important for interviews where you might be asked to explain basic sorting.
5

Selection Sort

Find Minimum, Swap, Repeat

Selection Sort works by repeatedly selecting the smallest element from the unsorted portion and moving it to the sorted portion. Think of it as finding the best card in your hand and placing it first.

How Selection Sort Works

🎯 Visual Walkthrough: Sorting [64, 25, 12, 22, 11]

Pass 1:Find min (11) → Swap with index 0 → [11, 25, 12, 22, 64]
Pass 2:Find min (12) → Swap with index 1 → [11, 12, 25, 22, 64]
Pass 3:Find min (22) → Swap with index 2 → [11, 12, 22, 25, 64]
Pass 4:Find min (25) → Already in place → [11, 12, 22, 25, 64] ✅
Selection Sort Algorithm
FUNCTION SelectionSort(array):
    n = array.length

    FOR i = 0 TO n-1:
        minIndex = i

        // Find minimum in unsorted portion
        FOR j = i+1 TO n-1:
            IF array[j] < array[minIndex]:
                minIndex = j

        // Swap minimum with first unsorted element
        SWAP(array[i], array[minIndex])

    RETURN array
END FUNCTION

Code Implementation (5 Languages)

1# Selection Sort in Python
2# Time: O(n²) | Space: O(1)
3
4def selection_sort(arr):
5 """
6 Sort by repeatedly finding minimum and placing at beginning.
7 """
8 n = len(arr)
9
10 for i in range(n):
11 # Find minimum element in unsorted portion
12 min_idx = i
13
14 for j in range(i + 1, n):
15 if arr[j] < arr[min_idx]:
16 min_idx = j
17
18 # Swap minimum with first unsorted position
19 arr[i], arr[min_idx] = arr[min_idx], arr[i]
20
21 return arr
22
23# Example
24arr = [64, 25, 12, 22, 11]
25print("Sorted:", selection_sort(arr))
26# Output: [11, 12, 22, 25, 64]
UTF-8Ln 26, Col 0

Complexity Analysis

MetricValue
Best CaseO(n²)
Average CaseO(n²)
Worst CaseO(n²)
SpaceO(1)
Stable?❌ No
In-Place?✅ Yes

Not Stable!

Selection Sort is not stable-it can change the relative order of equal elements. If stability matters (e.g., sorting by multiple fields), use Insertion Sort or Merge Sort instead.

Selection Sort vs Bubble Sort

AspectSelection SortBubble Sort
SwapsO(n) - fewer swapsO(n²) - many swaps
Best CaseO(n²)O(n)
Stable❌ No✅ Yes
Memory WritesFewerMore

Key Takeaway

Selection Sort performs fewer swaps than Bubble Sort (O(n) vs O(n²)), making it better when write operations are expensive (e.g., flash memory). However, it's still O(n²) overall and not suitable for large datasets.
6

Insertion Sort ⭐

Best for Small & Nearly Sorted Data

Insertion Sort builds the final sorted array one item at a time. It's like sorting playing cards in your hand-you pick each card and insert it into its correct position among the already-sorted cards.

Real-World Favorite

Despite being O(n²), Insertion Sort is often used in practice for small arrays or nearly-sorted data. Even languages like Python and Java use it as part of their hybrid sorting algorithms (TimSort) for small subarrays!

How Insertion Sort Works

🃏 Visual Walkthrough: Sorting [12, 11, 13, 5, 6]

Start:[12 | 11, 13, 5, 6] - First element is "sorted"
Insert 11:11 < 12 → Shift 12 right → [11, 12 | 13, 5, 6]
Insert 13:13 > 12 → Already in place → [11, 12, 13 | 5, 6]
Insert 5:5 < all → Shift all right → [5, 11, 12, 13 | 6]
Insert 6:6 goes after 5 → [5, 6, 11, 12, 13] ✅
Insertion Sort Algorithm
FUNCTION InsertionSort(array):
    n = array.length

    FOR i = 1 TO n-1:
        key = array[i]          // Current element to insert
        j = i - 1

        // Shift elements greater than key
        WHILE j >= 0 AND array[j] > key:
            array[j + 1] = array[j]
            j = j - 1

        // Insert key at correct position
        array[j + 1] = key

    RETURN array
END FUNCTION

Code Implementation (5 Languages)

1# Insertion Sort in Python
2# Time: O(n²) worst | O(n) best | Space: O(1)
3
4def insertion_sort(arr):
5 """
6 Sort by building sorted portion one element at a time.
7 Like sorting playing cards in your hand.
8 """
9 n = len(arr)
10
11 for i in range(1, n):
12 key = arr[i] # Element to insert
13 j = i - 1
14
15 # Shift elements greater than key to the right
16 while j >= 0 and arr[j] > key:
17 arr[j + 1] = arr[j]
18 j -= 1
19
20 # Insert key at correct position
21 arr[j + 1] = key
22
23 return arr
24
25# Example
26arr = [12, 11, 13, 5, 6]
27print("Sorted:", insertion_sort(arr))
28# Output: [5, 6, 11, 12, 13]
UTF-8Ln 28, Col 0

Complexity Analysis

MetricValue
Best CaseO(n)
Average CaseO(n²)
Worst CaseO(n²)
SpaceO(1)
Stable?✅ Yes
In-Place?✅ Yes

🚀 Why O(n) Best Case?

When the array is already sorted, the inner while loop never executes-each element is already greater than the previous one. We only do one comparison per element, giving us O(n).

This makes Insertion Sort ideal for nearly-sorted data or as a final pass after a more efficient algorithm.

When to Use Insertion Sort

✅ Perfect For:

  • • Small arrays (n < 50)
  • • Nearly sorted data
  • • Online sorting (data arrives one at a time)
  • • Stable sorting required
  • • Hybrid algorithms (final pass)

❌ Avoid For:

  • • Large random datasets
  • • Reverse-sorted data
  • • Performance-critical large sorts

Comparison: Simple Sorting Algorithms

AlgorithmBestAverageWorstStableBest Use
Bubble SortO(n)O(n²)O(n²)✅Educational
Selection SortO(n²)O(n²)O(n²)❌Minimize swaps
Insertion Sort ⭐O(n)O(n²)O(n²)✅Small/nearly sorted

Key Takeaway

Among simple O(n²) sorting algorithms, Insertion Sort is the most practical. Its O(n) best case for nearly-sorted data and stability make it valuable in real-world scenarios. It's used in production code (TimSort, IntroSort) as the final sorting pass for small subarrays.

7

Merge Sort ⭐⭐

Divide and Conquer Master

Merge Sort is a divide and conquer algorithm that divides the array into halves, recursively sorts them, and merges the sorted halves. It guarantees O(n log n) performance in all cases.

Guaranteed O(n log n)
Always consistent performance
Stable Sort
Preserves order of equal elements

How Merge Sort Works

The algorithm has two main steps: Divide (split array in half until single elements) and Conquer (merge sorted halves back together).

🌳 Divide & Conquer Visualization

📐 DIVIDE Phase:
[38, 27, 43, 3, 9, 82, 10]
↓ split ↓
[38, 27, 43]
[3, 9, 82, 10]
↓ split ↓
[38]
[27, 43]
[3, 9]
[82, 10]
🔗 CONQUER Phase (Merge):
[27, 43]
[3, 9]
[10, 82]
↑ merge ↑
[27, 38, 43]
[3, 9, 10, 82]
↑ merge ↑
[3, 9, 10, 27, 38, 43, 82] ✅
Merge Sort Algorithm
FUNCTION MergeSort(array):
    IF array.length <= 1:
        RETURN array

    // Divide
    mid = array.length / 2
    left = MergeSort(array[0...mid])
    right = MergeSort(array[mid...end])

    // Conquer
    RETURN Merge(left, right)

FUNCTION Merge(left, right):
    result = []
    i = j = 0

    WHILE i < left.length AND j < right.length:
        IF left[i] <= right[j]:
            result.append(left[i++])
        ELSE:
            result.append(right[j++])

    // Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])

    RETURN result

Code Implementation (5 Languages)

1# Merge Sort in Python
2# Time: O(n log n) | Space: O(n)
3
4def merge_sort(arr):
5 """
6 Divide and conquer sorting algorithm.
7 Splits array, sorts halves, merges back.
8 """
9 if len(arr) <= 1:
10 return arr
11
12 # Divide
13 mid = len(arr) // 2
14 left = merge_sort(arr[:mid])
15 right = merge_sort(arr[mid:])
16
17 # Conquer (merge)
18 return merge(left, right)
19
20def merge(left, right):
21 """
22 Merge two sorted arrays into one sorted array.
23 """
24 result = []
25 i = j = 0
26
27 while i < len(left) and j < len(right):
28 if left[i] <= right[j]:
29 result.append(left[i])
30 i += 1
31 else:
32 result.append(right[j])
33 j += 1
34
35 # Append remaining elements
36 result.extend(left[i:])
37 result.extend(right[j:])
38
39 return result
40
41# Example
42arr = [38, 27, 43, 3, 9, 82, 10]
43print("Sorted:", merge_sort(arr))
44# Output: [3, 9, 10, 27, 38, 43, 82]
UTF-8Ln 44, Col 0

Complexity Analysis

MetricValue
Best CaseO(n log n)
Average CaseO(n log n)
Worst CaseO(n log n)
SpaceO(n)
Stable?✅ Yes
In-Place?❌ No

🧮 Why O(n log n)?

log n splits: Array gets halved log₂(n) times until single elements

n merges per level: Each level processes all n elements during merge

Total: n × log n = O(n log n)

When to Use Merge Sort

✅ Perfect For:

  • • Linked lists (no random access needed)
  • • External sorting (files don't fit in memory)
  • • When stability is required
  • • When guaranteed O(n log n) is needed
  • • Parallel processing (easy to parallelize)

⚠️ Considerations:

  • • Requires O(n) extra space
  • • Slower than QuickSort in practice for arrays
  • • Higher constant factors than simpler sorts
  • • Cache performance not as good as in-place sorts

Industry Usage

Merge Sort forms the basis of TimSort, used by Python's sort() and Java's Arrays.sort() for objects. TimSort combines Merge Sort's guaranteed performance with Insertion Sort's efficiency for small arrays.

Key Takeaway

Merge Sort is the gold standard for stable, guaranteed O(n log n) sorting. Choose it when you need predictable performance, stability, or are sorting linked lists. The O(n) space tradeoff is worth it in many real-world scenarios.

8

Quick Sort ⭐⭐⭐

The King of Sorting Algorithms

Quick Sort is often considered the fastest general-purpose sorting algorithm in practice. It uses the divide and conquer strategy with a clever partitioning scheme that sorts in-place with O(1) auxiliary space.

Fastest in Practice
Excellent cache performance
In-Place
O(log n) stack space
O(n²) Worst Case
Poor pivot choice

How Quick Sort Works

Quick Sort works by selecting a pivot element and partitioning the array so that elements smaller than the pivot go left, and larger elements go right. Then it recursively sorts the partitions.

⚡ Partition Visualization: [10, 7, 8, 9, 1, 5]

Step 1:Choose pivot = 5 (last element)
Step 2:Partition: elements <5 go LEFT, elements >5 go RIGHT
Step 3:[1] | 5 | [10, 7, 8, 9] → Pivot in final position!
Step 4:Recursively sort [1] (done) and [10, 7, 8, 9]
Result:[1, 5, 7, 8, 9, 10] ✅
Quick Sort Algorithm
FUNCTION QuickSort(array, low, high):
    IF low < high:
        // Partition and get pivot index
        pivotIndex = Partition(array, low, high)

        // Recursively sort elements before and after pivot
        QuickSort(array, low, pivotIndex - 1)
        QuickSort(array, pivotIndex + 1, high)

FUNCTION Partition(array, low, high):
    pivot = array[high]    // Choose last element as pivot
    i = low - 1            // Index of smaller element

    FOR j = low TO high - 1:
        IF array[j] <= pivot:
            i = i + 1
            SWAP(array[i], array[j])

    SWAP(array[i + 1], array[high])
    RETURN i + 1            // Return pivot's final position

Code Implementation (5 Languages)

1# Quick Sort in Python
2# Time: O(n log n) avg, O(n²) worst | Space: O(log n)
3
4def quick_sort(arr):
5 """
6 Partition-based divide and conquer sorting.
7 Choose pivot, partition, recursively sort partitions.
8 """
9 if len(arr) <= 1:
10 return arr
11
12 # Choose pivot (using last element)
13 pivot = arr[-1]
14
15 # Partition into three lists
16 left = [x for x in arr[:-1] if x <= pivot]
17 right = [x for x in arr[:-1] if x > pivot]
18
19 # Recursively sort and combine
20 return quick_sort(left) + [pivot] + quick_sort(right)
21
22# In-place version (more efficient)
23def quick_sort_inplace(arr, low, high):
24 if low < high:
25 # Partition and get pivot index
26 pi = partition(arr, low, high)
27
28 # Recursively sort partitions
29 quick_sort_inplace(arr, low, pi - 1)
30 quick_sort_inplace(arr, pi + 1, high)
31
32def partition(arr, low, high):
33 pivot = arr[high] # Choose last element as pivot
34 i = low - 1 # Index of smaller element
35
36 for j in range(low, high):
37 if arr[j] <= pivot:
38 i += 1
39 arr[i], arr[j] = arr[j], arr[i]
40
41 arr[i + 1], arr[high] = arr[high], arr[i + 1]
42 return i + 1
43
44# Example
45arr = [10, 7, 8, 9, 1, 5]
46quick_sort_inplace(arr, 0, len(arr) - 1)
47print("Sorted:", arr) # [1, 5, 7, 8, 9, 10]
UTF-8Ln 47, Col 0

Complexity Analysis

MetricValue
Best CaseO(n log n)
Average CaseO(n log n)
Worst CaseO(n²)
SpaceO(log n)
Stable?❌ No
In-Place?✅ Yes

When Does O(n²) Happen?

The worst case occurs when:

  • • Array is already sorted (if picking first/last as pivot)
  • • Array is reverse sorted
  • • All elements are the same

Solution: Use randomized pivot or median-of-three pivot selection.

Pivot Selection Strategies

First/Last Element

Simple but poor for sorted data

❌ Not recommended
Random Element

Good average-case guarantee

✅ Recommended
Median-of-Three

Median of first, middle, last

✅ Best practice

Quick Sort vs Merge Sort

AspectQuick SortMerge Sort
Worst CaseO(n²)O(n log n)
SpaceO(log n)O(n)
Stable❌ No✅ Yes
In-Place✅ Yes❌ No
Cache PerformanceExcellentGood
Practical Speed⭐ FasterSlower

When to Use Quick Sort

✅ Perfect For:

  • • Arrays (excellent cache locality)
  • • Memory-constrained environments
  • • When average-case performance matters
  • • General-purpose sorting
  • • When you can use randomized pivot

❌ Avoid For:

  • • Linked lists (use Merge Sort)
  • • When stability is required
  • • Real-time systems (O(n²) worst case)
  • • Already sorted or nearly sorted data (without random pivot)

Industry Usage

Quick Sort (with modifications) is used by:
  • • C's qsort()
  • • C++ STL's std::sort() (Introsort variant)
  • • Java's Arrays.sort() for primitives
  • • Many database query engines

Key Takeaway

Quick Sort is the go-to sorting algorithm for production code when working with arrays. Its excellent cache performance and in-place nature make it faster than Merge Sort in practice, despite the O(n²) worst case. Always use randomized or median-of-three pivot to avoid worst-case scenarios.

9

Algorithm Comparison Charts

Master Reference Tables

Use these comparison tables as your quick reference guide for choosing the right algorithm. Bookmark this section for interviews and technical discussions!

🔍 Searching Algorithms

AlgorithmBestAvgWorstSpaceStable?
Linear SearchO(1)O(n)O(n)O(1)✅
Binary SearchO(1)O(log n)O(log n)O(1)✅
Jump SearchO(1)O(√n)O(√n)O(1)✅
Interpolation SearchO(1)O(log log n)O(n)O(1)✅

📊 Sorting Algorithms

AlgorithmBestAvgWorstSpaceStable?
Bubble SortO(n)O(n²)O(n²)O(1)✅
Selection SortO(n²)O(n²)O(n²)O(1)❌
Insertion Sort ⭐O(n)O(n²)O(n²)O(1)✅
Merge Sort ⭐⭐O(n log n)O(n log n)O(n log n)O(n)✅
Quick Sort ⭐⭐⭐O(n log n)O(n log n)O(n²)O(log n)❌
Heap SortO(n log n)O(n log n)O(n log n)O(1)❌
Counting SortO(n+k)O(n+k)O(n+k)O(k)✅
Radix SortO(nk)O(nk)O(nk)O(n+k)✅

🤔 How to Choose the Right Algorithm

Decision Tree for Sorting

Q: Is stability required?
Yes → Use Merge Sort or Insertion Sort
No → Continue...
Q: Is data size small (n < 50)?
Yes → Use Insertion Sort
No → Continue...
Q: Is data nearly sorted?
Yes → Use Insertion Sort or TimSort
No → Continue...
Q: Is memory a constraint?
Yes → Use Quick Sort or Heap Sort
No → Use Merge Sort
Default Choice: Quick Sort (with random pivot)

⚡ Quick Reference Cards

For Arrays (Random Access)

  • 🔍 Search: Binary Search
  • 📊 Sort (general): Quick Sort
  • 📊 Sort (stable): Merge Sort
  • 📊 Sort (small n): Insertion Sort

For Linked Lists (Sequential)

  • 🔍 Search: Linear Search
  • 📊 Sort: Merge Sort
  • ❌ Avoid: Quick Sort, Binary Search

For Integers (Limited Range)

  • 📊 Sort: Counting Sort (O(n+k))
  • 📊 Sort (larger range): Radix Sort
  • ✅ Beats O(n log n) comparison-based sorts!

For External Sorting (Disk)

  • 📊 Sort: External Merge Sort
  • 📊 Reason: Sequential disk access
  • ❌ Avoid: Quick Sort (random access)

Key Takeaway

No single algorithm is best for all scenarios. Understanding the trade-offs between time, space, stability, and access patterns is key to making the right choice. When in doubt, Quick Sort for arrays and Merge Sort for linked lists are safe defaults.

10

Frequently Asked Questions

Interview & Common Doubts

Answers to the most common questions about searching and sorting algorithms-from interview prep to real-world implementation decisions.

What's the fastest sorting algorithm?
It depends! Quick Sort is fastest for general-purpose sorting of arrays due to excellent cache performance. However, for integers with limited range, Counting Sort (O(n+k)) or Radix Sort (O(nk)) can be faster. For linked lists, Merge Sort is best. Always consider your specific use case.
Why is Quick Sort preferred over Merge Sort for arrays?
Quick Sort has better cache locality since it operates in-place and accesses memory sequentially. It also uses less memory (O(log n) vs O(n)). Although Merge Sort has guaranteed O(n log n), Quick Sort's practical performance is typically 2-3x faster for arrays.
When should I use Binary Search?
Use Binary Search when your data is sorted and you need to search multiple times. If the data is unsorted, you'd need to sort it first (O(n log n)), which is only worth it if you'll search many times. For a single search on unsorted data, Linear Search is fine.
What does 'stable sort' mean and why does it matter?
A stable sort maintains the relative order of equal elements. This matters when sorting by multiple keys-e.g., sort students by name, then by grade. A stable sort preserves the name order within each grade. Merge Sort and Insertion Sort are stable; Quick Sort and Heap Sort are not.
What's the difference between in-place and out-of-place sorting?
In-place algorithms (Quick Sort, Heap Sort) modify the original array with O(1) extra space. Out-of-place algorithms (Merge Sort) require O(n) additional space for temporary arrays. In-place is better for memory-constrained environments.
How do I handle duplicate elements in Binary Search?
Standard Binary Search returns any matching index. To find the first occurrence, continue searching left after finding a match. To find the last occurrence, search right. These are called lower_bound and upper_bound variations.
Why is Bubble Sort taught if it's so inefficient?
Bubble Sort is educational-it clearly demonstrates comparison and swapping concepts. Understanding why it's inefficient (many unnecessary comparisons) helps appreciate why Quick Sort and Merge Sort are better. It's also easy to implement and debug.
What is the best algorithm for nearly sorted data?
Insertion Sort is excellent for nearly sorted data with O(n) best-case complexity. TimSort (used by Python and Java) is also optimized for real-world data that often has pre-sorted runs.
Can I use Binary Search on a linked list?
Technically yes, but it's inefficient. Binary Search requires O(1) random access to find the middle element. In a linked list, finding the middle takes O(n), making the overall complexity O(n log n)-worse than Linear Search's O(n). Use Linear Search for linked lists.
What sorting algorithm do programming languages use internally?
Most languages use hybrid algorithms: Python and Java use TimSort (Merge Sort + Insertion Sort). C++ STL uses IntroSort (Quick Sort + Heap Sort + Insertion Sort). These combine multiple algorithms' strengths.
How do I sort objects by multiple fields?
Use a stable sort and sort by secondary key first, then primary key. Alternatively, use a custom comparator that compares the primary key first, then the secondary key if primary keys are equal.
What's the space complexity of recursive algorithms?
Recursive algorithms use stack space proportional to recursion depth. Quick Sort uses O(log n) stack space (average). Merge Sort uses O(log n) stack space plus O(n) for temporary arrays. Tail-recursive algorithms can sometimes be optimized to O(1) space.

Conclusion & Next Steps

Your Roadmap Forward

Congratulations! You've completed a comprehensive journey through the most fundamental algorithms in computer science. Let's recap what you've learned and outline your next steps.

Searching Algorithms

  • Linear Search - O(n) for unsorted data
  • Binary Search - O(log n) for sorted data
  • When to use each approach

Simple Sorting Algorithms

  • Bubble Sort - Educational baseline
  • Selection Sort - Minimize swaps
  • Insertion Sort - Best for small/nearly sorted

Advanced Sorting Algorithms

  • Merge Sort - Stable, guaranteed O(n log n)
  • Quick Sort - Fastest in practice
  • Algorithm trade-offs & comparisons

Key Concepts

  • Big O complexity analysis
  • Time vs Space trade-offs
  • Stability and in-place sorting

🎯 Key Takeaways

1

Binary Search is essential-it appears in 30%+ of coding interviews and is the foundation for many advanced algorithms.

2

Quick Sort is the go-to for general sorting, but always use randomized pivot selection to avoid O(n²) worst case.

3

Merge Sort is your friend when stability matters or when sorting linked lists and external data.

4

Insertion Sort isn't just educational-it's used in production as part of hybrid algorithms like TimSort.

5

Understanding WHY an algorithm works is more important than memorizing code. Focus on the core logic.

📚 What to Learn Next

Advanced Data Structures

Intermediate

Trees, Graphs, Hash Tables

Dynamic Programming

Advanced

Optimization problems

Graph Algorithms

Intermediate

BFS, DFS, Dijkstra

Advanced Sorting

Intermediate

Heap Sort, Counting Sort, Radix Sort

Practice Makes Perfect

The best way to solidify your understanding is through practice. Try implementing each algorithm from scratch without looking at the code. Solve problems on LeetCode, HackerRank, or Codeforces that use these algorithms.

🚀 Ready to Level Up?

Stay updated with more DSA guides, interview tips, and coding tutorials. Follow for regular updates on algorithms, data structures, and software engineering.

Enjoyed this article?Leave a reaction

Tap multiple times to show love!

Tags

#DSA#Algorithms#Sorting#Searching#Interview#Python#Java#C++#JavaScript#Binary Search#Quick Sort#Merge Sort
Dev Kant Kumar

Dev Kant Kumar

Author

Full Stack Developer passionate about crafting high-performance user experiences. I write about Agentic AI, React, and the future of web development.

💬 Discussion