text: 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 MethodsSorting Methods
  Focus Problem – try your best to solve this problem before continuing!
  Library SortingLibrary Sorting
  Although you usually do not need to know how sorting is implemented, you should know how to use built-in methods.
  C++
  Java
  Python
  Static ArraysStatic Arrays
  C++
  To sort static arrays, use
  sort(arr, arr + N) where 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 .
  #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
  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
  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
  Longinstead of
  long. This forces the
  Arrays.sort()function to use mergesort, which is always .
  -
  Dynamic ArraysDynamic 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 .
  #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}}
  Python
  In order to sort a list, simply use the
  sorted(list) function.
  (Dynamic) Arrays of Pairs & Tuples(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.
  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
  ProblemsProblems
  Warning!
  Bronze problems are designed that you shouldn't need a time sort (repeatedly extracting the minimum in time will always suffice).
  Note: There are some more sorting problems in the Intro to Sets module.
  Check Your UnderstandingCheck Your Understanding
  What would the array 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!