# 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 |

### Static Arrays

C++

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

In order 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.

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.

### 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());for (int i : v)cout << i << " "; //1 2 3 4 5cout << endl;v = {5, 1, 3, 2, 4};sort(v.begin() + 1, v.begin() + 4);for (int i : v)cout << i << " "; //5 1 2 3 4}

Java

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

. The default sort
function sorts the array in ascending order.

import java.util.*;class Main{public static void main (String[] args){ArrayList<Integer> arr = new ArrayList<Integer>();arr.add(5); arr.add(1); arr.add(3); arr.add(2); arr.add(4);Collections.sort(arr);for (int i : arr)System.out.print(i + " "); //1 2 3 4 5}}

### (Dynamic) Arrays of Pairs & Tuples

C++

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

// Source: CPH#include <bits/stdc++.h>using namespace std;int main() {vector<pair<int,int>> v;v.push_back({1,5});v.push_back({2,3});v.push_back({1,2});

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.

list = [(1, 2), (2, 3), (2, 1), (3, 1)]list = sorted(list)for x, y in list:print(f'{x}, {y}')# Output:# 1, 2# 2, 1# 2, 3# 3, 1

## Problems

### Warning!

Bronze problems are designed 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 | Normal | ## Show TagsGreedy, Sorting | |||

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

Bronze | Hard | ## Show TagsSimulation, 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!