Skip to content

Introduction to Sorting

This page briefly introduces sorting algorithms.

Definition

A sorting algorithm is an algorithm that arranges a given collection of data in some order. There are many sorting algorithms, and most of them differ in their properties.

Properties

Stability

Stability is about whether sorting changes the relative order of equal elements.

A stable algorithm keeps records with equal keys in their original relative order. That is, if a sorting algorithm is stable and two records \(R\) and \(S\) have equal keys, with \(R\) before \(S\) in the original list, then \(R\) is also before \(S\) in the sorted list.

Radix sort, counting sort, insertion sort, bubble sort and merge sort are stable sorts.

Selection sort, heapsort, quicksort and Shellsort are not stable sorts.

Time complexity

Main page: Complexity

Time complexity measures how an algorithm's running time depends on its input size. It is usually written with \(O\).

A simple way to work out a complexity is to count the number of times "simple operations" are executed. Sometimes you can get a rough estimate just by counting how deeply the loops are nested.

An algorithm has a best-case time complexity, an average-case time complexity and a worst-case time complexity. In OI contests you usually care about the worst case, because it is a lower bound on how well the algorithm performs: nothing worse can happen during judging.

Any comparison-based algorithm that sorts \(n\) arbitrary distinct elements needs \(\Omega(n\log n)\) comparisons in the worst case.

Of course, not every sorting algorithm is \(O(n\log n)\). For example, counting sort runs in \(O(n+w)\), where \(w\) is the size of the value range of the input.

The following compares several sorting algorithms.

Comparison of several sorting algorithms

Space complexity

Like time complexity, space complexity describes how much space an algorithm uses. In general, the lower the space complexity, the better the algorithm.