What is a sorting algorithm?

In computer science, a sorting algorithm refers to a procedure for ordering elements in a list by repeating a sequence of steps. These algorithms are a vital component of many applications, such as search tools, data analysis, and e-commerce. They arrange a list of items in numerical order (from least to greatest or vice versa) or lexicographical/dictionary order (a generalization of alphabetical order) to make the list more usable. Sorting algorithms are evaluated by their computational complexity, which is a measure of the time and memory the algorithm requires to function.

Why do we use sorting algorithms in computer science?

Sorting algorithms arrange list elements in numerical or lexicographical order, making the list more usable. They are crucial in various applications like search tools, data analysis, and e-commerce. These algorithms are evaluated by their computational complexity, which measures the time and memory the algorithm requires to function. Quicksort and merge sort are favored for their relatively low computational complexity.

What are some common types of sorting algorithms?

Sorting algorithms arrange list elements in a specific order, such as numerical or lexicographical. These algorithms are crucial for data analysis, search tools, and e-commerce. Common sorting algorithms include: * Selection sort It finds the minimum element in an unsorted list and swaps it with the first element, repeating until sorted. Selection sort is intuitive but has a quadratic time complexity of (O(n^2)). * Insertion sort Builds a sorted list by inserting elements from the unsorted list into their correct positions. Like selection sort, it has an average time complexity of (O(n^2)), but performs better with nearly sorted lists. * Merge sort Employs a divide-and-conquer strategy, splitting the list into sublists, sorting them, and then merging them back together. Merge sort operates in (O(n \log n)) time. * Quicksort Chooses a 'pivot' element and partitions the other elements. The complexity of Quicksort depends on the order of the list. It generally averages (O(n \log n)) time, but can degrade to (O(n^2)).

How does the bubble sort algorithm work?

The bubble sort algorithm is a simple method for ordering elements in a list sorting algorithm . It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until no more swaps are needed, indicating that the list is sorted. Although easy to understand and implement, bubble sort is not very efficient for large datasets, with a computational complexity of O(n^2).

How do we measure the efficiency of a sorting algorithm?

The efficiency of a sorting algorithm is primarily measured by its computational complexity, reflecting the time and memory the algorithm needs to function. Computer scientists use big-O notation to describe how quickly these resource costs grow as the problem size increases. Time complexity is typically written as T(n), where n relates to the input size. Big-O notation describes the growth order as the number of elements increases. For example, O(n^2) (quadratic time) indicates the time to sort grows with the square of the list's length n , whereas O(n log n) is more efficient. Algorithms with polynomial time complexity are considered efficient, while those with exponential growth are labeled intractable due to their impracticality.

What are some situations where a specific sorting algorithm is better to use than others?

Different sorting algorithms offer advantages in specific scenarios, depending on factors such as data size, pre-sortedness, and memory constraints.

sorting algorithm

Introduction References & Edit History Related Topics

Images

A chart compares the steps of four sorting algorithms-selection sort, insertion sort, merge sort, and quicksort-using color-coded numbers to illustrate how the sequence 8, 5, 1, 3, 7 is sorted by each method.

A step-by-step diagram of selection sort using the list 8, 5, 1, 3, 7, with green highlighting the current placement position and yellow marking the minimum number found at each step, resulting in a sorted sequence.

Step-by-step diagram showing how the insertion sort algorithm arranges the numbers 8, 5, 1, 3, 7. Blue highlights the current number being sorted, while red indicates sorted numbers.

A step-by-step diagram showing merge sort, with the numbers 8, 5, 1, 3, 7 being grouped and divided by vertical lines, then gradually rearranged until sorted as 1, 3, 5, 7, 8.

A step-by-step diagram of the Quicksort algorithm sorting the numbers 8, 5, 1, 3, 7, with each row showing the current pivot in purple and previously used pivots in orange.

Quick Facts

Related Topics:: algorithm; sorting

On the Web:: Engineering LibreTexts - Sorting Algorithms (Oct. 17, 2026)

See all related content

sorting algorithm

computer science

Written by

Stephen Eldridge

Fact-checked by

Britannica Editors

Last updated

Oct. 17, 2026 •History

Top Questions

What is a sorting algorithm?
In computer science, a sorting algorithm refers to a procedure for ordering elements in a list by repeating a sequence of steps. These algorithms are a vital component of many applications, such as search tools, data analysis, and e-commerce. They arrange a list of items in numerical order (from least to greatest or vice versa) or lexicographical/dictionary order (a generalization of alphabetical order) to make the list more usable.

Sorting algorithms are evaluated by their computational complexity, which is a measure of the time and memory the algorithm requires to function.
1 Britannica Source
1. sorting algorithm
Created from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.
Why do we use sorting algorithms in computer science?
Sorting algorithms arrange list elements in numerical or lexicographical order, making the list more usable. They are crucial in various applications like search tools, data analysis, and e-commerce. These algorithms are evaluated by their computational complexity, which measures the time and memory the algorithm requires to function. Quicksort and merge sort are favored for their relatively low computational complexity.
1 Britannica Source
1. sorting algorithm
Created from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.
What are some common types of sorting algorithms?
Sorting algorithms arrange list elements in a specific order, such as numerical or lexicographical. These algorithms are crucial for data analysis, search tools, and e-commerce.

Common sorting algorithms include:
* Selection sort It finds the minimum element in an unsorted list and swaps it with the first element, repeating until sorted. Selection sort is intuitive but has a quadratic time complexity of (O(n^2)).
* Insertion sort Builds a sorted list by inserting elements from the unsorted list into their correct positions. Like selection sort, it has an average time complexity of (O(n^2)), but performs better with nearly sorted lists.
* Merge sort Employs a divide-and-conquer strategy, splitting the list into sublists, sorting them, and then merging them back together. Merge sort operates in (O(n \log n)) time.
* Quicksort Chooses a 'pivot' element and partitions the other elements. The complexity of Quicksort depends on the order of the list. It generally averages (O(n \log n)) time, but can degrade to (O(n^2)).
1 Britannica Source
1. sorting algorithm
Created from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.
How does the bubble sort algorithm work?
The bubble sort algorithm is a simple method for ordering elements in a list sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until no more swaps are needed, indicating that the list is sorted. Although easy to understand and implement, bubble sort is not very efficient for large datasets, with a computational complexity of O(n^2).
1 Britannica Source
1. sorting algorithm
Created from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.
How do we measure the efficiency of a sorting algorithm?
The efficiency of a sorting algorithm is primarily measured by its computational complexity, reflecting the time and memory the algorithm needs to function. Computer scientists use big-O notation to describe how quickly these resource costs grow as the problem size increases.

Time complexity is typically written as T(n), where n relates to the input size. Big-O notation describes the growth order as the number of elements increases. For example, O(n^2) (quadratic time) indicates the time to sort grows with the square of the list's length n, whereas O(n log n) is more efficient.

Algorithms with polynomial time complexity are considered efficient, while those with exponential growth are labeled intractable due to their impracticality.
2 Britannica Sources
1. time complexity
2. sorting algorithm
Created from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.
What are some situations where a specific sorting algorithm is better to use than others?
Different sorting algorithms offer advantages in specific scenarios, depending on factors such as data size, pre-sortedness, and memory constraints.
- Insertion sort: Efficient for small datasets or nearly sorted data because it has a low overhead and adapts well to existing order.
- Merge sort: Guarantees (O(n \log n)) time complexity, making it suitable for large datasets when consistent performance is crucial. It divides the list into sublists and merges them back in sorted order.
- Quicksort: Generally fast in practice, with an average time complexity of (O(n \log n)), but its worst-case performance is (O(n^2)), which occurs with already sorted or reverse-sorted data. It works by choosing a 'pivot' element and partitioning the other elements.
- Selection sort: Simple and intuitive but inefficient for large datasets due to its (O(n^2)) time complexity. It repeatedly finds the minimum element from the unsorted part and places it at the beginning.
1 Britannica Source
1. sorting algorithm
Created from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.

sorting algorithm, in computer science, a procedure for ordering elements in a list by repeating a sequence of steps. Sorting algorithms allow a list of items to be sorted so that the list is more usable than it was, usually by placing the items in numerical order (from the least value to the greatest or vice versa) or lexicographical order (also called dictionary order, a generalization of alphabetical order). Sorting algorithms are a vital building block of many other applications, including search tools, data analysis, and e-commerce. There are many sorting algorithms, but most applications use sorts with relatively low computational complexity—for example, Quicksort or merge sort.

In computer science, an algorithm is a procedure for solving a computational problem. For a problem to be solved with an algorithm, it must be clearly defined so that the accuracy of the algorithm can be evaluated. In the case of sorting, this is generally straightforward, as the elements are typically sorted in one of two well-defined ways. One way is numerical order, which is based on some numerical value the elements possess. Sorting dates from earliest to latest, sorting physicians by patient ratings from highest to lowest, or sorting items for sale in a store from least to most expensive are all examples of numerical sorting. The other common way of sorting is lexicographical order, or dictionary order, which is how alphanumeric string values are typically sorted. In most cases, this is equivalent to alphabetical order, though it is possible to use alternative rules to sort dictionaries of elements.

One of the key ways sorting algorithms are evaluated is by their computational complexity—a measure of how much time and memory a particular algorithm requires to function. Because the actual time and space requirements vary depending on the specifics of the problem being solved (e.g., sorting a hundred items or a million), computer scientists use big-O notation to describe how quickly resource costs grow as the size of the problem grows. The O of big-O notation refers to the order, or kind, of growth the function experiences. O(1), for example, indicates that the complexity of the algorithm is constant, while O(n) indicates that the complexity of the problem grows in a linear fashion as n increases, where n is a variable related to the size of the problem—for example, the length of the list to be sorted. The O value of a particular algorithm may also depend upon the specifics of the problem, so it is sometimes analyzed for best-case, worst-case, and average scenarios.

Sorting algorithms can be described in several ways. Some algorithms are stable, meaning that the order of equivalent elements will be preserved, while others are unstable, meaning that the order may not be preserved. For example, if a database of personal contacts is sorted first by name and then by address, a stable sort algorithm will ensure that people living at the same address remain alphabetized by name within each address.

Sorting algorithms can also be divided into comparison algorithms, which sort by comparing one element in a list to another, and non-comparison algorithms, which find other ways to sort. Non-comparison algorithms are sometimes less computationally complex than even the best comparison algorithms, but they are often limited in other ways. For example, a counting sort has lower time requirements than any comparison sort, but it can be applied only to integers. The examples given below are comparison algorithms.

One simple sorting algorithm is known as selection sort. In this algorithm, the sort function analyzes an unsorted list to find the first element—typically the minimum—then swaps it with the first element in the list. It then analyzes the unsorted part of the list again to find the new minimum element and swaps it with the first element in the unsorted part of the list. It repeats this process until each element in the list has been sorted. For example, consider the list {8,5,1,3,7}. The algorithm sorts the list into {1,5,8,3,7} by switching the 8 and the 1 and continues until the list is completely sorted.

Selection sort is relatively intuitive, resembling the way many people sort elements in their daily lives. However, it is also computationally complex. A pass through the list must occur for every element in the list, and, during each pass, every unsorted element must be evaluated to find the minimum. Consequently, selection sort uses O(n²), or quadratic time, where n is the length of the list. This notation means that the time it takes to sort a list grows in proportion to the square of the length of the list.

Explore Britannica Premium!

The trusted destination for professionals, college students, and lifelong learners.

A similar sorting method, insertion sort, involves building a sorted list at the beginning of the unsorted list. Each element in the unsorted list is inserted in its correct place in the sorted list. In the list {8,5,1,3,7}, the first step is to place the 5 before the 8 to make {5,8,1,3,7}.

Like selection sort, insertion sort uses O(n²) time on average, but, in its best case, it is much quicker than selection sort. For an already sorted list, insertion sort uses O(n) time, because it must compare each item only to the previous one to find the item’s place.

A more efficient algorithm than insertion sort is merge sort. Merge sort uses a divide-and-conquer approach, splitting an unsorted list into two sublists and continuing to split the sublists in that fashion until each has one or fewer elements. Then the algorithm iteratively merges the sublists in sorted order until the entire list is sorted. The list {8,5,1,3,7} is thus split into five sublists of one element each that are then merged back into one sorted list.

Merge sort uses O(n logn) time, which is significantly more efficient than O(n²). The amount of time required grows with the length of the list multiplied by the log, or logarithm, of the length, because the number of iterations required depends on how many times the list must be divided in half.

Another popular divide-and-conquer sort algorithm is Quicksort. In Quicksort, one of the values in a list is chosen as a “pivot.” Each other value on the list is then compared with the pivot and placed either before it, if it is smaller, or after it, if it is greater. Then a new pivot is chosen for each of the unsorted sublists, and they are organized in the same fashion. This process is repeated until the entire list is sorted. In the list {8,5,1,3,7}, 1 may be chosen as the pivot, resulting in {1,8,5,3,7}. The number 5 may be chosen as the next pivot, leading to {1,3,5,8,7}, and, with 8 as the next pivot, the list is fully sorted.

Unlike merge sort, the computational complexity of Quicksort is highly dependent on the existing order of the list to be sorted. In most cases, Quicksort will average out to O(n logn) time, like merge sort. However, if a list happens to be ordered backward (e.g., from greatest to least when one intends to sort from least to greatest), Quicksort uses O(n²) time.

Stephen Eldridge

sorting algorithm

Thank you for signing up!