Sorting Algorithm
- In Turkish
- Sıralama Algoritması
In short
A sorting algorithm is a step-by-step method for arranging items in a defined order, such as numbers from smallest to largest or names alphabetically.
What is a sorting algorithm?
A sorting algorithm puts the items of a list in order according to a rule, such as numeric, alphabetical, or by date. Sorting matters because many other tasks become much faster on sorted data, including binary search, removing duplicates, merging lists, and finding the median. Algorithms are compared by their time complexity, the extra memory they need, and whether they are stable.
Simple algorithms such as bubble sort, selection sort, and insertion sort take O(n^2) time on average, which becomes slow for large lists, although insertion sort is still fast on small or nearly sorted input. Merge sort splits the list in half, sorts each half, and merges the results in O(n log n) time using O(n) extra memory. Quicksort picks a pivot and partitions the items around it, averaging O(n log n) but falling to O(n^2) in the worst case, while heap sort guarantees O(n log n) with O(1) extra memory. Any algorithm that sorts only by comparing items needs on the order of n log n comparisons in the worst case, but counting sort and radix sort can beat that for integers or short keys because they don't compare items directly.
Sorting a hand of playing cards is a good analogy: most people pick up one card at a time and slide it into the right place among the cards they already hold, which is exactly how insertion sort works. In real code you rarely write your own sort. Python's sorted() and list.sort() use Timsort, a hybrid of merge sort and insertion sort, and modern JavaScript engines use similar stable O(n log n) algorithms for Array.prototype.sort().
Stability is a frequent source of confusion. A stable sort keeps items with equal keys in their original relative order, so if you sort orders by date and then stably by customer, each customer's orders stay in date order. Python's sort is stable, and JavaScript's has been required to be stable since ES2019. In JavaScript, calling sort() without a compare function converts items to strings, so [10, 9, 1].sort() returns [1, 10, 9]; pass (a, b) => a - b to sort numbers by value.
Key takeaways
- Simple sorts like bubble, selection, and insertion sort run in O(n^2) time.
- Merge sort and heap sort run in O(n log n) time even in the worst case; quicksort averages O(n log n) but can hit O(n^2).
- Sorting by comparisons alone can't beat O(n log n) in the worst case.
- A stable sort keeps equal items in their original order.
- Prefer your language's built-in sort, which is fast and well tested.
Example
def insertion_sort(items):
# O(n^2) in the worst case, but close to O(n) on nearly sorted input
for i in range(1, len(items)):
current = items[i]
j = i - 1
# Shift larger items one step right to make room for current
while j >= 0 and items[j] > current:
items[j + 1] = items[j]
j -= 1
items[j + 1] = current
return items
print(insertion_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]
print(sorted([5, 2, 9, 1, 5, 6])) # built-in, O(n log n): same resultReaders ask
What is the fastest sorting algorithm?
No single algorithm is fastest for every input. For general-purpose sorting, O(n log n) hybrids such as Timsort and introsort, which combine several simpler algorithms, are the practical choice, while counting sort and radix sort can be faster for integers in a limited range.
Why does JavaScript sort numbers incorrectly?
By default, Array.prototype.sort() converts elements to strings and compares them character by character, so 10 comes before 9. Pass a compare function such as (a, b) => a - b to sort numbers by value.
What does it mean for a sorting algorithm to be stable?
A stable algorithm keeps items that compare as equal in the same relative order they had before sorting. This matters when you sort records by one field and then by another, because the first ordering survives within each group of the second.
See also
- AlgorithmProgramming Fundamentals, p. 2An algorithm is a finite, step-by-step set of instructions for solving a problem or completing a task, such as sorting a list or finding the shortest route.
- Big O NotationProgramming Fundamentals, p. 6Big O notation describes how an algorithm's running time or memory use grows as its input gets larger, focusing on the growth rate rather than exact speed.
- Binary SearchData Structures, p. 5Binary search is an algorithm that finds a value in a sorted list by repeatedly halving the search range, taking O(log n) time instead of checking every item.
- HeapData Structures, p. 19A heap is a tree-based data structure that keeps the smallest or largest item at its root, so you can read it in O(1) and remove it in O(log n) time.
- RecursionProgramming Fundamentals, p. 48Recursion is a technique in which a function solves a problem by calling itself on smaller versions of the same problem until it reaches a simple base case.
- ArrayProgramming Fundamentals, p. 3An array is an ordered collection of values stored under one name, where each item is accessed by its numeric position, called an index, usually starting at 0.
- Bubble SortData Structures, p. 9Bubble sort is a simple sorting algorithm that keeps swapping out-of-order neighbors, so each pass carries the largest remaining value to the end.
- Insertion SortData Structures, p. 20Insertion sort builds a sorted list one element at a time, putting each new one in its place among those already sorted, like sorting cards in your hand.
Spotted a mistake or something missing on this page?Suggest an edit