Algorithm
Sorting algorithms put data in order: merge sort, quicksort, heapsort, stability, the n log n lower bound, counting and radix sort, and built-in sorts.
Sorting rearranges elements into a defined order such as numeric, alphabetical or chronological. Algorithms fall into two families: comparison sorts (bubble, insertion, selection, merge, quick and heap sort), which only ask whether one element comes before another, and non-comparison sorts such as counting sort and radix sort, which use integer values or their digits directly.
Sorting is the preparation step for binary search, deduplication, interval merging, rankings and much more, which is why it is among the first algorithms people study. Knowing the Ω(n log n) lower bound for comparison sorts, the difference between stable and in-place sorts, and how built-in sorts behave, such as Python's Timsort or the introsort used by most C++ std::sort implementations, helps you make the right call in production code and in coding interviews.
A good way to study it is to trace insertion sort, merge sort and quicksort by hand on small arrays, then implement merge sort and quicksort yourself and compare their best, average and worst cases. After that, practice sorting with key functions and comparators, and solve problems built on sorting, such as merging intervals and counting inversions.
Merge sort splits the input in half and merges the halves; quicksort partitions around a pivot. Both run in O(n log n) on average.
A stable sort keeps elements with equal keys in their original order; an in-place sort needs almost no extra memory. Which one matters more depends on the task.
A decision-tree argument shows that any comparison sort needs on the order of n log n comparisons in the worst case. Merge sort and heapsort reach this bound.
Counting sort and radix sort order integers with a limited range or number of digits in near-linear time, without comparing elements to each other.
merge_sort splits the list in half, sorts each half recursively, then merges the two sorted halves by repeatedly taking the smaller front element. Taking the left element on ties (<=) makes it stable, and it runs in O(n log n) for any input. The last line checks the result against the built-in sorted().
merge_sort.py
def merge_sort(items):
"""Return a new sorted list (stable, O(n log n))."""
if len(items) <= 1:
return list(items)
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # take the left one on ties: stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort(data) == sorted(data)) # True
python merge_sort.pySix chapters that take you from installation to the core ideas of Sorting.
Ask questions, share experience and trade opinions about Sorting.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.