Sorting is the process of arranging elements in a specific order, typically in ascending or descending order. Understanding sorting algorithms is crucial as they form the basis for many other algorithms and are frequently used in real-world applications.
- In-place Sorting: Algorithm uses O(1) extra space
- Stable Sorting: Preserves relative order of equal elements
- Comparison Sort: Uses element comparisons to sort
- Non-comparison Sort: Uses element properties to sort
- Adaptive Sort: Performance improves with presorted data
- Internal Sort: All data fits in main memory
- External Sort: Data needs to be retrieved from external storage
- Natural Sort: Exploits existing order in the data
- Hybrid Sort: Combines multiple sorting algorithms
| Algorithm | Best | Average | Worst | Space | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | No |
| Radix Sort | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | Yes | No |
| Shell Sort | O(n log n) | O(n^1.3) | O(n²) | O(1) | No | Yes |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
Where:
- n = number of elements
- k = range of elements
- d = number of digits
def quick_sort(arr, low, high):
def partition(low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
if low < high:
pi = partition(low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)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 resultdef heap_sort(arr):
def heapify(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(n, largest)
n = len(arr)
# Build max heap
for i in range(n // 2 - 1, -1, -1):
heapify(n, i)
# Extract elements from heap
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(i, 0)def counting_sort(arr):
if not arr:
return arr
# Find range of array elements
max_val = max(arr)
min_val = min(arr)
range_val = max_val - min_val + 1
# Initialize counting array and output array
count = [0] * range_val
output = [0] * len(arr)
# Store count of each element
for num in arr:
count[num - min_val] += 1
# Modify count array to store actual positions
for i in range(1, len(count)):
count[i] += count[i - 1]
# Build output array
for num in reversed(arr):
index = count[num - min_val] - 1
output[index] = num
count[num - min_val] -= 1
return outputdef sort_colors(nums):
low = mid = 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1def custom_sort(arr):
return sorted(arr, key=lambda x: (priority(x), x))
# Example: Sort strings by length then lexicographically
strings = ["banana", "apple", "cherry"]
sorted_strings = sorted(strings, key=lambda x: (len(x), x))- Empty array
- Single element array
- Array with all identical elements
- Array already sorted
- Array sorted in reverse
- Array with negative numbers
- Array with floating point numbers
- Very large arrays
- Arrays with duplicates
- Arrays with special characters
- Not handling empty or single-element arrays
- Incorrect pivot selection in QuickSort
- Stack overflow in recursive implementations
- Not considering stability requirements
- Inefficient handling of duplicates
- Memory leaks in implementations
- Incorrect boundary conditions
- Sort Array By Parity (LC #905)
- Height Checker (LC #1051)
- Sort Array by Increasing Frequency (LC #1636)
- Sort Colors (LC #75)
- Sort Characters By Frequency (LC #451)
- Custom Sort String (LC #791)
- Sort the Matrix Diagonally (LC #1329)
- First Missing Positive (LC #41)
- Maximum Gap (LC #164)
- Count of Smaller Numbers After Self (LC #315)
- Database Systems: Indexing and query optimization
- File Systems: File organization
- Operating Systems: Process scheduling
- Graphics: Rendering order
- Text Processing: Dictionary ordering
- Network Routing: Packet scheduling
- Computational Biology: Genome sequencing
- External Sorting:
- Multi-way merge
- Replacement selection
- Parallel Sorting:
- Parallel merge sort
- Bitonic sort
- Specialized Sorting:
- Network sorting
- Pancake sorting
- String Sorting:
- Radix sort variations
- Suffix arrays
- Online Sorting:
- Insertion streams
- Priority queues
- Sorting Algorithms Visualizations
- Python's Timsort Implementation
- Comparison of Sorting Algorithms
- External Sorting Tutorial
- Parallel Sorting Algorithms
- Clarify input constraints
- Consider stability requirements
- Analyze space complexity needs
- Choose appropriate algorithm
- Handle edge cases explicitly
- Consider optimization opportunities
- Test with small examples
- Discuss trade-offs between algorithms