Sorting Techniques
Expert Answer & Key Takeaways
Comprehensive guide to Sorting Algorithms: Bubble, Selection, Insertion, Merge, Quick, and Heap sort with complexity analysis.
Sorting Techniques in Data Structures
Sorting is the process of arranging a collection of data (like an array or a linked list) into a specific order, most commonly in numerical (ascending or descending) or lexicographical order. Sorting significantly optimizes the usefulness of data and is often a required precursor to search algorithms like Binary Search.
1. Important Sorting Concepts
- In-place Sorting: An algorithm is in-place if it requires a constant amount O(1) of extra memory space to sort the data (e.g., Bubble Sort, Quick Sort). Algorithms like Merge Sort require O(N) extra space and are not in-place.
- Stable Sorting: A sorting algorithm is stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array. (e.g., Merge Sort, Insertion Sort, Bubble Sort).
- Unstable Sorting: The relative order of records with equal keys might change (e.g., Quick Sort, Heap Sort, Selection Sort).
2. Bubble Sort
Bubble Sort is the simplest sorting algorithm. It works by repeatedly swapping the adjacent elements if they are in the wrong order.
2.1 Algorithm
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
bool swapped = false;
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
if (swapped == false) break; // Optimization
}
}2.2 Complexity
- Best Case: O(N) (when the array is already sorted and optimized with a
swappedflag). - Worst / Average Case: O(N^2).
- Space: O(1) (In-place).
- Stability: Stable.
3. Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.
3.1 Algorithm
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}3.2 Complexity
- Best / Worst / Average Case: O(N^2) (It scans the unsorted part completely every time).
- Space: O(1) (In-place).
- Stability: Unstable (default implementation).
4. Insertion Sort
Insertion sort works the way we sort playing cards in our hands. It virtually splits the array into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
4.1 Algorithm
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}4.2 Complexity
- Best Case: O(N) (when array is already sorted).
- Worst / Average Case: O(N^2).
- Space: O(1) (In-place).
- Stability: Stable.
5. Merge Sort
Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
5.1 Complexity
- Best / Worst / Average Case: O(N log N).
- Space: O(N) (Requires extra space for the temporary arrays during merging).
- Stability: Stable.
6. Quick Sort
Quick Sort is also a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. Elements smaller than pivot go left, and elements greater go right.
6.1 Complexity
- Best / Average Case: O(N log N).
- Worst Case: O(N^2) (Occurs when the pivot chosen is always the greatest or smallest element, typically if the array is already sorted and the last/first element is chosen as pivot).
- Space: O(log N) (Call stack for recursion).
- Stability: Unstable.
7. Heap Sort
Heap sort is a comparison-based sorting technique based on the Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end.
7.1 Complexity
- Best / Worst / Average Case: O(N log N).
- Space: O(1) (In-place).
- Stability: Unstable.
8. Summary & Comparison Table
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(N) | O(N^2) | O(N^2) | O(1) | Yes |
| Selection Sort | O(N^2) | O(N^2) | O(N^2) | O(1) | No |
| Insertion Sort | O(N) | O(N^2) | O(N^2) | O(1) | Yes |
| Merge Sort | O(N log N) | O(N log N) | O(N log N) | O(N) | Yes |
| Quick Sort | O(N log N) | O(N log N) | O(N^2) | O(log N) | No |
| Heap Sort | O(N log N) | O(N log N) | O(N log N) | O(1) | No |
Course4All Editorial Board
Verified ExpertSubject Matter Experts
Comprising experienced educators and curriculum specialists dedicated to providing accurate, exam-aligned preparation material.
Pattern: 2026 Ready
Updated: Weekly
Found an issue or have a suggestion?
Help us improve! Report bugs or suggest new features on our Telegram group.