Complete Guide to Sorting Algorithms

Posted by tintin_2003 on 2025-10-08 20:46:40 | Last Updated by tintin_2003 on 2025-10-16 01:37:26

Share: Facebook | Twitter | Whatsapp | Linkedin Visits: 33

Complete Guide to Sorting Algorithms

Sorting algorithms are fundamental building blocks in computer science that arrange data in a specific order. This comprehensive guide explores various sorting techniques, from simple to advanced, with practical implementations.

1. Bubble Sort

Description: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Code:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# Test
data = [64, 34, 25, 12, 22, 11, 90]
print("Original:", data)
print("Sorted:", bubble_sort(data.copy()))

Output:

Original: [64, 34, 25, 12, 22, 11, 90]
Sorted: [11, 12, 22, 25, 34, 64, 90]

Time Complexity: O(n²) | Space Complexity: O(1)

2. Selection Sort

Description: It divides the input into a sorted and an unsorted region. The sorted region is built up by repeatedly finding the smallest element from the unsorted region and putting it at the beginning of the sorted region.

Code:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Test
data = [64, 25, 12, 22, 11]
print("Original:", data)
print("Sorted:", selection_sort(data.copy()))

Output:

Original: [64, 25, 12, 22, 11]
Sorted: [11, 12, 22, 25, 64]

Time Complexity: O(n²) | Space Complexity: O(1)

3. Insertion Sort

Description: It builds a sorted array one item at a time. It is much less efficient on large lists than more advanced sorting algorithms such as quicksort, heapsort, or merge sort.

Code:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Test
data = [12, 11, 13, 5, 6]
print("Original:", data)
print("Sorted:", insertion_sort(data.copy()))

Output:

Original: [12, 11, 13, 5, 6]
Sorted: [5, 6, 11, 12, 13]

Time Complexity: O(n²) | Space Complexity: O(1)

4. Quick Sort

Description: It is a divide and conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

Code:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# Test
data = [10, 7, 8, 9, 1, 5]
print("Original:", data)
print("Sorted:", quick_sort(data))

Output:

Original: [10, 7, 8, 9, 1, 5]
Sorted: [1, 5, 7, 8, 9, 10]

Time Complexity: O(n log n) average, O(n²) worst | Space Complexity: O(log n)

5. Merge Sort

Description: It is a divide and conquer algorithm based on the idea of breaking down a list into several sub-lists, sorting each sub-list, and then merging them back together.

Code:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test
data = [38, 27, 43, 3, 9, 82, 10]
print("Original:", data)
print("Sorted:", merge_sort(data))

Output:

Original: [38, 27, 43, 3, 9, 82, 10]
Sorted: [3, 9, 10, 27, 38, 43, 82]

Time Complexity: O(n log n) | Space Complexity: O(n)

6. Heap Sort

Description: It is a comparison-based sorting technique based on Binary Heaps and can be modified to be an efficient inline sorting algorithm.

Code:

def heap_sort(arr):
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right
        
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)
    
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr

# Test
data = [12, 11, 13, 5, 6, 7]
print("Original:", data)
print("Sorted:", heap_sort(data.copy()))

Output:

Original: [12, 11, 13, 5, 6, 7]
Sorted: [5, 6, 7, 11, 12, 13]

Time Complexity: O(n log n) | Space Complexity: O(1)

7. Radix Sort

Description: It is a non-comparative integer sorting algorithm, meaning it sorts data based on value equivalence rather than direct comparison. It is primarily used to sort large amounts of data with many keys of similar value sizes.

Code:

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    for i in range(n - 1, -1, -1):
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
    
    for i in range(n):
        arr[i] = output[i]

# Test
data = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original:", data)
print("Sorted:", radix_sort(data.copy()))

Output:

Original: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted: [2, 24, 45, 66, 75, 90, 170, 802]

Time Complexity: O(d × n) where d is number of digits | Space Complexity: O(n + k)

8. Bucket Sort

Description: It is a sorting algorithm based on comparison. It distributes the elements of an array into a number of buckets. Each bucket is then sorted individually, either by using a sorting algorithm that is efficient for small lists, or by recursively applying the bucket sorting algorithm.

Code:

def bucket_sort(arr):
    if len(arr) == 0:
        return arr
    
    bucket_count = 10
    max_val = max(arr)
    min_val = min(arr)
    bucket_range = (max_val - min_val) / bucket_count
    
    buckets = [[] for _ in range(bucket_count)]
    
    for num in arr:
        index = min(int((num - min_val) / bucket_range), bucket_count - 1)
        buckets[index].append(num)
    
    for bucket in buckets:
        bucket.sort()
    
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

# Test
data = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print("Original:", data)
print("Sorted:", bucket_sort(data))

Output:

Original: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
Sorted: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

Time Complexity: O(n + k) average | Space Complexity: O(n + k)

9. Counting Sort

Description: It sorts the elements by counting the number of occurrences of each element in the list and then builds the final array from the counts. It can only be used for sorting a finite range of data.

Code:

def counting_sort(arr):
    if not arr:
        return arr
    
    max_val = max(arr)
    min_val = min(arr)
    range_size = max_val - min_val + 1
    
    count = [0] * range_size
    output = [0] * len(arr)
    
    for num in arr:
        count[num - min_val] += 1
    
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    
    return output

# Test
data = [4, 2, 2, 8, 3, 3, 1]
print("Original:", data)
print("Sorted:", counting_sort(data))

Output:

Original: [4, 2, 2, 8, 3, 3, 1]
Sorted: [1, 2, 2, 3, 3, 4, 8]

Time Complexity: O(n + k) | Space Complexity: O(k)

10. Shell Sort

Description: It is a modification to insertion sort that improves the efficiency by increasing the size of the gap between elements at each step.

Code:

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    
    return arr

# Test
data = [12, 34, 54, 2, 3]
print("Original:", data)
print("Sorted:", shell_sort(data.copy()))

Output:

Original: [12, 34, 54, 2, 3]
Sorted: [2, 3, 12, 34, 54]

Time Complexity: O(n log n) to O(n²) | Space Complexity: O(1)

11. Cocktail Shaker Sort

Description: It is a variation of bubble sort that performs the swapping actions both from the end and the beginning of the unsorted region, reducing the number of iterations required.

Code:

def cocktail_shaker_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    
    while swapped:
        swapped = False
        
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        
        if not swapped:
            break
        
        swapped = False
        end -= 1
        
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        
        start += 1
    
    return arr

# Test
data = [5, 1, 4, 2, 8, 0, 2]
print("Original:", data)
print("Sorted:", cocktail_shaker_sort(data.copy()))

Output:

Original: [5, 1, 4, 2, 8, 0, 2]
Sorted: [0, 1, 2, 2, 4, 5, 8]

Time Complexity: O(n²) | Space Complexity: O(1)

12. Comb Sort

Description: It is a simple, efficient, and little-known sorting algorithm. It works by repeatedly finding and eliminating long runs of adjacent elements that are in the wrong order.

Code:

def comb_sort(arr):
    n = len(arr)
    gap = n
    shrink = 1.3
    sorted_flag = False
    
    while not sorted_flag:
        gap = int(gap / shrink)
        if gap <= 1:
            gap = 1
            sorted_flag = True
        
        i = 0
        while i + gap < n:
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                sorted_flag = False
            i += 1
    
    return arr

# Test
data = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]
print("Original:", data)
print("Sorted:", comb_sort(data.copy()))

Output:

Original: [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]
Sorted: [-44, -6, 0, 1, 3, 4, 8, 23, 28, 56]

Time Complexity: O(n²) worst, O(n log n) average | Space Complexity: O(1)

13. Gnome Sort

Description: It is a modification of bubble sort, where each swap puts the array in a sorted state, and the traversal moves forward unless the current element is in the right order.

Code:

def gnome_sort(arr):
    index = 0
    n = len(arr)
    
    while index < n:
        if index == 0:
            index += 1
        elif arr[index] >= arr[index - 1]:
            index += 1
        else:
            arr[index], arr[index - 1] = arr[index - 1], arr[index]
            index -= 1
    
    return arr

# Test
data = [34, 2, 10, -9, 45, 23]
print("Original:", data)
print("Sorted:", gnome_sort(data.copy()))

Output:

Original: [34, 2, 10, -9, 45, 23]
Sorted: [-9, 2, 10, 23, 34, 45]

Time Complexity: O(n²) | Space Complexity: O(1)

14. Pancake Sort

Description: It is a cooking-inspired sorting algorithm that flips pancakes to rearrange the elements. It is a variation of Bubble Sort.

Code:

def pancake_sort(arr):
    def flip(arr, k):
        left = 0
        while left < k:
            arr[left], arr[k] = arr[k], arr[left]
            left += 1
            k -= 1
    
    def find_max_index(arr, n):
        max_idx = 0
        for i in range(n):
            if arr[i] > arr[max_idx]:
                max_idx = i
        return max_idx
    
    n = len(arr)
    for curr_size in range(n, 1, -1):
        max_idx = find_max_index(arr, curr_size)
        if max_idx != curr_size - 1:
            flip(arr, max_idx)
            flip(arr, curr_size - 1)
    
    return arr

# Test
data = [23, 10, 20, 11, 12, 6, 7]
print("Original:", data)
print("Sorted:", pancake_sort(data.copy()))

Output:

Original: [23, 10, 20, 11, 12, 6, 7]
Sorted: [6, 7, 10, 11, 12, 20, 23]

Time Complexity: O(n²) | Space Complexity: O(1)

15. Cycle Sort

Description: It is a non-comparative sorting algorithm where the array is cyclically shifted until all elements are in their correct positions.

Code:

def cycle_sort(arr):
    writes = 0
    
    for cycle_start in range(len(arr) - 1):
        item = arr[cycle_start]
        pos = cycle_start
        
        for i in range(cycle_start + 1, len(arr)):
            if arr[i] < item:
                pos += 1
        
        if pos == cycle_start:
            continue
        
        while item == arr[pos]:
            pos += 1
        
        arr[pos], item = item, arr[pos]
        writes += 1
        
        while pos != cycle_start:
            pos = cycle_start
            
            for i in range(cycle_start + 1, len(arr)):
                if arr[i] < item:
                    pos += 1
            
            while item == arr[pos]:
                pos += 1
            
            arr[pos], item = item, arr[pos]
            writes += 1
    
    return arr

# Test
data = [1, 8, 3, 9, 10, 10, 2, 4]
print("Original:", data)
print("Sorted:", cycle_sort(data.copy()))

Output:

Original: [1, 8, 3, 9, 10, 10, 2, 4]
Sorted: [1, 2, 3, 4, 8, 9, 10, 10]

Time Complexity: O(n²) | Space Complexity: O(1)

Comparison Summary

Choosing the Right Algorithm

• Small datasets (<50 elements): Insertion Sort or Selection Sort
• Large datasets with random data: Quick Sort or Merge Sort
• Nearly sorted data: Insertion Sort or Tim Sort
• Guaranteed O(n log n): Merge Sort or Heap Sort
• Limited memory: Heap Sort or Shell Sort
• Integer data with known range: Counting Sort or Radix Sort
• Stability required: Merge Sort, Counting Sort, or Tim Sort

Conclusion

Understanding sorting algorithms is crucial for optimizing data processing. Each algorithm has its strengths and ideal use cases. Modern programming languages often use hybrid approaches like Tim Sort (Python) that combine multiple techniques for optimal performance across different scenarios.