Sorting Algorithms
Sorting is the process of arranging data in a particular order (usually ascending or descending). Efficient sorting is critical for optimizing the performance of other algorithms (like search) that require sorted input data.
1. 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.
- Time Complexity: $O(n \log n)$ in all cases (Best, Average, Worst).
- Space Complexity: $O(n)$ (requires auxiliary space for merging).
- Stability: Stable (preserves the relative order of equal elements).
How it Works
- Divide: Find the middle point to divide the array into two halves.
- Conquer: Recursively call
mergeSortfor the first half and the second half. - Combine: Merge the two halves sorted in step 2.
Implementation (Python)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
return merge(merge_sort(left_half), merge_sort(right_half))
def merge(left, right):
sorted_arr = []
i = j = 0
# Compare elements from both lists and add the smaller one
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
# Add remaining elements
sorted_arr.extend(left[i:])
sorted_arr.extend(right[j:])
return sorted_arr2. 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.
- Time Complexity: $O(n \log n)$ on average, but $O(n^2)$ in the worst case (rare, happens if the pivot is always the smallest/largest element).
- Space Complexity: $O(\log n)$ (stack space for recursion).
- Stability: Unstable (relative order of equal elements might change).
How it Works
- Pick Pivot: Choose an element (e.g., the last element).
- Partition: Reorder the array so that all elements with values less than the pivot come before the pivot, and all elements with values greater than the pivot come after it.
- Recursion: Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
Implementation (Python)
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)3. Comparison
| Algorithm | Time (Avg) | Time (Worst) | Space | Stable? | Best For |
|---|---|---|---|---|---|
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | Linked Lists, large datasets where stability matters. |
| Quick Sort | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | No | Arrays, general purpose in-memory sorting. |
| Bubble Sort | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Small datasets, educational purposes. |
programming/algorithms programming/recursion programming/arrays-and-lists