PrevNext
Not Frequent
 0/8

Introduction to Sorting

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

Arranging collections in increasing order.

Edit This Page

Sorting refers to arranging items in some particular order.

Sorting Methods

Bubble Sort
HR - Very Easy

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

Resources
CPH
3.1 - Sorting Theory

bubble sort, merge sort, counting sort

CSA
Sorting

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
3.2 - Sorting in C++

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

CPP
std::sort

reference

CF
C++ Tricks

first two related to sorting

Java

Resources
tutorialspoint
Java sorting

Covers sorting arrays

Oracle
Arrays.sort

API for sorting static arrays

Oracle
Collections.sort

API for sorting dynamic arrays

Python

Resources
PY
Sorting HOW TO

reference

C++

Static Arrays

To sort static arrays, use sort(arr, arr + N) where NN 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)[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 5
	cout << 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 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.

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 O(Nlog⁡N)\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)[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 5
	for (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 array


arr.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 O(Nlog⁡N)\mathcal{O}(N\log N) time sort (repeatedly extracting the minimum in O(N2)\mathcal{O}(N^2) time will always suffice).

StatusSourceProblem NameDifficultyTags
CSES
Distinct Numbers
Easy
Show TagsSorting
CF
Playing in a Casino
Easy
Show TagsSorting
CF
Kayaking
Normal
Show TagsGreedy, Sorting
Bronze
Why Did the Cow Cross the Road III
Normal
Show TagsSimulation, Sorting
Bronze
Cow College
Normal
Show TagsSorting
Bronze
Angry Cows
Hard
Show TagsSimulation, Sorting
CF
Permutator
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][7, 2, 6, 3, 1] be after 1 pass of bubble sort?

Question 1 of 4

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!

Join Forum
PrevNext