Sorting Algorithms

Sorting is the process of arranging data in a particular order (ascending or descending).

Introduction

Sorting is one of the most fundamental operations in computer science. Understanding different sorting algorithms helps in choosing the right one for specific scenarios.

Comparison-Based Sorting

Bubble Sort

Repeatedly steps through the list, compares adjacent elements and swaps them if in wrong order.

Time Complexity: O(n²) Space Complexity: O(1) Stable: Yes

Selection Sort

Finds minimum element and places it at beginning, repeats for remaining elements.

Time Complexity: O(n²) Space Complexity: O(1) Stable: No

Insertion Sort

Builds sorted array one item at a time, inserting each element in correct position.

Time Complexity: O(n²) worst, O(n) best Space Complexity: O(1) Stable: Yes

Merge Sort

Divide and conquer algorithm that divides array into halves, sorts them, and merges.

Time Complexity: O(n log n) Space Complexity: O(n) Stable: Yes

Quick Sort

Picks pivot, partitions array around pivot, recursively sorts partitions.

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

Heap Sort

Uses binary heap data structure to sort elements.

Time Complexity: O(n log n) Space Complexity: O(1) Stable: No

Non-Comparison Sorting

Counting Sort

Counts occurrences of each element, uses count to determine position.

Time Complexity: O(n + k) where k is range Space Complexity: O(k) Stable: Yes

Radix Sort

Sorts numbers by processing individual digits.

Time Complexity: O(d × (n + k)) where d is digits Space Complexity: O(n + k) Stable: Yes

Bucket Sort

Distributes elements into buckets, sorts buckets individually.

Time Complexity: O(n + k) average Space Complexity: O(n) Stable: Yes

Algorithm Comparison

When to Use Which?

• Small arrays: Insertion Sort
• Nearly sorted: Insertion Sort or Bubble Sort
• General purpose: Quick Sort or Merge Sort
• Stability required: Merge Sort
• Limited memory: Heap Sort
• Integer sorting: Counting Sort or Radix Sort