Not Frequent

Introduction to Sorting

Authors: Darren Yao, Benjamin Qi, Allen Li

Sorting, and maintaining collections of distinct elements with ordered sets.

Sorting refers to arranging items in some particular order.


Bronze problems are (almost always) designed that you shouldn't need to sort, though the concept can come in very handy for some problems. This module is optional for Bronze contestants.

Sorting Methods

Focus Problem – read through this problem before continuing!

CPHbubble sort, merge sort, counting sort
CSAselection 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.


CPHcan stop before user-defined structs, which are covered in silver
CFfirst two related to sorting


tutorialspointCovers sorting arrays



(Dynamic) Arrays


In order to sort a dynamic array, use sort(v.begin(), v.end()) (or sort(begin(v),end(v))), whereas static arrays require sort(arr, arr + N) where NN is the number of elements to be sorted. The default sort function sorts the array in ascending order.


In order to sort a static or dynamic array, use Arrays.sort(arr) or Collections.sort(list) respectively. The default sort function sorts the array in ascending order.


The Arrays.sort() function uses quicksort on primitive data types such as longs. 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 Θ(N2)\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 O(NlogN)\mathcal{O}(N \log N).
  • Shuffle the array beforehand.


In order to sort a list, simply use the sorted(list) function.

(Dynamic) Arrays of Pairs & Tuples


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;

Tuples are sorted similarly.


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


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


StatusSourceProblem NameDifficultyTagsSolutionURL
CFEasyCheck CF

Note: For "Why Did the Cow Cross the Road III", you need a custom comparator for Java. This is covered in Silver.

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

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!

Give Us Feedback on Introduction to Sorting!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.