# Introduction to Sorting

Authors: Darren Yao, Benjamin Qi, Allen Li, Andrew Wang

Arranging collections in increasing order.

**Sorting** refers to arranging items in some particular order.

## Sorting Methods

Focus Problem – try your best to solve this problem before continuing!

Resources | ||||
---|---|---|---|---|

CPH | bubble sort, merge sort, counting sort | |||

CSA | selection sort, insertion sort, bubble sort, merge sort |

## Library Sorting

Although you usually do **not** need to know how sorting is implemented, you
should know how to use built-in methods.

C++

Resources | ||||
---|---|---|---|---|

CPH | can stop before user-defined structs, which are covered in silver | |||

CPP | reference | |||

CF | first two related to sorting |

Java

Resources | ||||
---|---|---|---|---|

tutorialspoint | Covers sorting arrays | |||

Oracle | API for sorting static arrays | |||

Oracle | API for sorting dynamic arrays |

Python

Resources | ||||
---|---|---|---|---|

PY | reference |

C++

### Static Arrays

To sort static arrays, use `sort(arr, arr + N)`

where $N$ is the number of
elements to be sorted. The range can also be specified by replacing `arr`

and
`arr + N`

with the intended range. For example, `sort(arr + 1, arr + 4)`

sorts
indices $[1, 4)$.

#include <bits/stdc++.h>using namespace std;int main() {int arr[] = {5, 1, 3, 2, 4};int N = 5;sort(arr, arr + N);for (int i = 0; i < N; i++) cout << arr[i] << " "; // 1 2 3 4 5cout << endl;int arr2[] = {5, 1, 3, 2, 4};sort(arr2 + 1, arr2 + 4);for (int i = 0; i < N; i++) cout << arr2[i] << " "; // 5 1 2 3 4}

Java

### Static Arrays

To sort a static array, use `Arrays.sort(arr)`

.

import java.util.*;class Main {public static void main(String[] args) {int arr[] = {5, 1, 3, 2, 4};Arrays.sort(arr);for (int i = 0; i < arr.length; i++)System.out.print(arr[i] + " "); // 1 2 3 4 5}}

### Warning!

The `Arrays.sort()`

function uses quicksort on primitive data types such as
`long`

s. This is fine for USACO, but in other contests such as Codeforces, it
may time out on test cases specifically engineered to trigger worst-case
$\Theta(N^2)$ behavior in quicksort. See here
for an example of a solution that was hacked on Codeforces.

There are two ways to avoid this:

- Declare the underlying array as an array of objects, for example
`Long`

instead of`long`

. This forces the`Arrays.sort()`

function to use mergesort, which is always $\mathcal{O}(N \log N)$. - Shuffle the array beforehand.

Note: The generator for the hack above works for OpenJDK 13 and below. In OpenJDK 14, heapsort is used if quicksort takes too long (source).

### Dynamic Arrays

C++

In order to sort a dynamic array, use `sort(v.begin(), v.end())`

(or
`sort(begin(v),end(v))`

). The default sort function sorts the array in ascending
order. Similarly, we can specify the range. For example,
`sort(v.begin() + 1, v.begin() + 4)`

sorts indices $[1, 4)$.

#include <bits/stdc++.h>using namespace std;int main() {vector<int> v{5, 1, 3, 2, 4};sort(v.begin(), v.end());// Outputs 1 2 3 4 5for (int i : v) { cout << i << " "; }cout << endl;

Java

In order to sort a dynamic array, use `Collections.sort(list)`

. This function
sorts the array in ascending order by default.

import java.util.*;class Main {public static void main(String[] args) {List<Integer> arr =new ArrayList<Integer>(Arrays.asList(5, 1, 3, 2, 4));Collections.sort(arr);System.out.println(arr); // Outputs [1, 2, 3, 4, 5]}}

Python

There's two main ways to sort a list in Python.
You can use `sorted(arr)`

, which returns a new list and doesn't modify the old
one, or `arr.sort()`

, which sorts the list in place.

arr = [5, 1, 3, 2, 4]print(sorted(arr)) # Outputs [1, 2, 3, 4, 5]print(arr) # Outputs the original arrayarr.sort()print(arr) # Outputs [1, 2, 3, 4, 5]

For more on sorting in Python, see this link.

### (Dynamic) Arrays of Pairs & Tuples

C++

By default, C++ pairs are sorted by first element and then second element in case of a tie.

#include <bits/stdc++.h>using namespace std;int main() {vector<pair<int, int>> v{{1, 5}, {2, 3}, {1, 2}};sort(v.begin(), v.end());/** Outputs:* 1 2* 1 5* 2 3*/for (pair<int, int> p : v) { cout << p.first << " " << p.second << endl; }}

Tuples are sorted similarly.

Java

You'll need to define your own **custom comparator**. This is covered in
Silver.

Python

By default, Python tuples sort by first element, then second element, and so on in case of repeated ties.

arr = [(1, 5), (2, 3), (1, 2)]arr = sorted(arr)print(arr) # Outputs [(1, 2), (1, 5), (2, 3)]

## Problems

### Warning!

Bronze problems are designed so that you shouldn't need a $\mathcal{O}(N\log N)$ time sort (repeatedly extracting the minimum in $\mathcal{O}(N^2)$ time will always suffice).

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsSorting | |||

CF | Easy | ## Show TagsSorting | |||

CF | Normal | ## Show TagsGreedy, Sorting | |||

Bronze | Normal | ## Show TagsSimulation, Sorting | |||

Bronze | Normal | ## Show TagsSorting | |||

Bronze | Hard | ## Show TagsSimulation, Sorting | |||

CF | Hard | ## Show TagsGreedy, Sorting |

Note: There are some more sorting problems in the Intro to Sets module.

## Check Your Understanding

What would the array $[7, 2, 6, 3, 1]$ be after 1 pass of bubble sort?

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!