Table of Contents:
Searching Algorithms & Sorting Algorithms – Concepts, Examples, and Time Complexity
Searching and sorting are two of the most fundamental concepts in computer science. They help you efficiently locate and organize data, forming the backbone of complex applications such as search engines, databases, e-commerce platforms, file systems, and operating systems.
This chapter explains the core concepts, techniques, examples, complexity, and practical uses of searching and sorting algorithms.
1. Searching Algorithms
A searching algorithm finds the position of a target value within a data structure such as an array or list.
Searching falls under two main categories:
1.1 Linear Search
Linear Search (Sequential Search) checks each element one-by-one.
How it works
for each element in array:
if element == target:
return index
Example
Array: [10, 25, 35, 50]
Search for: 35
It checks sequentially and finds the value at index 2.
Time Complexity
- Best Case: O(1)
- Worst Case: O(n)
- Space Complexity: O(1)
When to Use
- Small datasets
- Unsorted lists
1.2 Binary Search
Binary Search works only on sorted data. It divides the list into halves repeatedly until the value is found.
How it works
- Find mid
- Compare mid with target
- Eliminate half of the array
- Repeat
Example
Array: [5, 10, 15, 20, 25, 30]
Search for: 20
Steps:
- mid → 15 → too small
- search right half
- mid → 20 → match
Time Complexity
- Best Case: O(1)
- Worst Case: O(log n)
- Space: O(1)
When to Use
- Large datasets
- Sorted arrays
2. Sorting Algorithms
Sorting arranges data in a specific order (ascending or descending). Sorting improves efficiency of search operations and is heavily used in databases, libraries, and operating system schedulers.
Sorting algorithms fall into:
- Simple (Basic)
- Efficient (Advanced)
- Specialized
2.1 Bubble Sort
Compares adjacent elements and swaps them if needed.
How it works
repeat:
swap adjacent if out of order
until no swaps needed
Example
Input: 5 3 2 4
Pass 1 → 3 2 4 5
Pass 2 → 2 3 4 5
Time Complexity
- Worst: O(n²)
- Best: O(n)
- Space: O(1)
2.2 Selection Sort
Repeatedly selects the smallest (or largest) element and places it in the correct position.
How it works
for i from 0 to n-1:
find smallest element
swap with i
Time Complexity
- Worst: O(n²)
- Best: O(n²)
- Space: O(1)
2.3 Insertion Sort
Builds a sorted list one element at a time.
How it works
take element
compare with sorted section
insert in correct position
Time Complexity
- Worst: O(n²)
- Best: O(n)
- Space: O(1)
When to Use
- Nearly sorted data
- Small datasets
2.4 Merge Sort
A divide-and-conquer sorting algorithm.
How it works
- Split array into halves
- Recursively sort the halves
- Merge them
Time Complexity
- Best, Average, Worst: O(n log n)
- Space: O(n)
Features
- Stable
- Efficient for large lists
2.5 Quick Sort
Another divide-and-conquer method.
How it works
- Choose pivot
- Partition array
- Recursively sort left and right parts
Time Complexity
- Best/Average: O(n log n)
- Worst: O(n²) (rare)
- Space: O(log n)
Why It’s Popular
- Fast in practice
- Used widely in standard libraries
2.6 Heap Sort
Uses a binary heap to sort elements.
How it works
- Build max heap
- Swap root with last
- Reduce heap size
- Heapify
Time Complexity
- Best: O(n log n)
- Worst: O(n log n)
- Space: O(1)
Use Case
When stable O(n log n) sorting is needed without extra memory.
2.7 Counting Sort
Suitable for integer-based data with small range.
Complexity
- Time: O(n + k)
- Space: O(k)
Used for:
- Grades
- Age groups
- Fixed-range numbers
3. Best Sorting Algorithms Comparison
| Algorithm | Best | Worst | Space | Stability | Suitable For |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(1) | Yes | Teaching |
| Selection Sort | O(n²) | O(n²) | O(1) | No | Small fixed-size datasets |
| Insertion Sort | O(n) | O(n²) | O(1) | Yes | Nearly-sorted data |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes | Large datasets |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No | Most real-world uses |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No | Memory-limited apps |
| Counting Sort | O(n+k) | O(n+k) | O(k) | Yes | Narrow integer ranges |
searching algorithms, sorting algorithms, linear search, binary search, bubble sort, insertion sort, merge sort, quick sort, heap sort, counting sort, algorithm complexity, data structures, computer programming
4. Real-World Applications
Searching
- Search engines
- File systems
- Database indexes
- E-commerce product search
Sorting
- Leaderboards & rankings
- Data analysis
- Scheduling tasks
- Organizing contacts/files
- Autocomplete suggestions
FAQ
1. What is the difference between searching and sorting?
Searching finds an element; sorting arranges elements in a specific order.
2. Which searching algorithm is faster?
Binary Search — but only for sorted data.
3. Which sorting algorithm is best for large datasets?
Merge Sort or Quick Sort.
4. Is Bubble Sort used in real applications?
Rarely — mainly used for learning.
5. Why does Quick Sort perform well in practice?
Because it has excellent cache performance and low overhead.
6. What is the fastest sorting algorithm?
There’s no single fastest; it depends on:
- data size
- data distribution
- memory constraints
7. Which languages support these algorithms?
All (C, C++, Java, Python, PHP, JavaScript, etc.) — they may even include built-in optimized versions.