Native Sort¶

Time Complexity	Space Complexity
Varies, see notes	Varies, see notes

Regardless of whether you learn the different sorting methods, it’s good to know how to use your language’s native sort. It will come up, and typically it’s a one-liner.

Methods are included for standard arrays and preferred array types, if applicable. They all output “1, 2, 3, 4, 5”.

#include <iostream>
#include <vector>
using namespace std;

int main(){
  int arr[] = {1, 5, 2, 4, 3};
  int n = sizeof(arr)/sizeof(arr[0]);
  sort(arr, arr+n);
  for (int i = 0; i < n; ++i)
    cout << arr[i] << " ";
  cout << endl;

  //Vector method
  vector<int> vec{1, 5, 2, 4, 3};       //C++ 11 line
  sort(vec.begin(), vec.end());
  for(int i = 0; i < vec.size(); i++)
    cout << vec[i] << " ";

  return 0;
}

using System;
using System.Collections.Generic;

class Program{
  static void Main(string[] args){
    int[] arr = new int[] {1, 5, 2, 4, 3};
    Array.Sort(arr);
    for (int i = 0; i < arr.Length; ++i)
      Console.Write(arr[i] + " ");
    Console.Write("\n");

    //List
    List<int> list = new List<int> {1, 5, 2, 4, 3};
    list.Sort();
    for(int i = 0; i < list.Count; i++)
      Console.Write(list[i] + " ");
  }
}

import java.util.*;

public class nativeSort {
  public static void main(String[] args) {
    int[] arr = {1, 5, 2, 4, 3};
    Arrays.sort(arr);
    System.out.println(Arrays.toString(arr));

    //arraylist
    List<Integer> arrList = new ArrayList<Integer>(Arrays.asList(1,5,2,4,3));
    Collections.sort(arrList);
    System.out.println(arrList);
  }
}

var arr = [1, 5, 2, 4, 3];
arr.sort();
console.log(arr);

arr = [1, 5, 2, 4, 3]
arr.sort()
print(arr)

var arr = [1, 5, 2, 4, 3]
arr.sort()
print(arr)

Notes¶

The native sort in C++ sorts with two pointers, a pointer to the beginning and end of the array. For a standard array, the beginning pointer is just the array variable (arr here). The ending pointer, however, is typed with the syntax array + number of items, where the + number of items tells the compiler to shift the pointer over by the size of the type of array times (*) the number of items in the array.

Since C++ doesn’t have a way of getting the number of items in an array, the following is typically used:

int size = sizeof(array) / sizeof(array[0]);

This works because the size of the array in bytes divided by the size of the type in bytes yields the number of items in the array, typically. Then, to sort:

sort(array, array + size);

For a vector, the start and end pointers are known and stored, so those are used:

sort(vector.begin(), vector.end());

Note

There is one line marked as C++ 11 here, so add “-std=c++11” after “g++” when compiling if it doesn’t work.

If you’re stuck with an older version of C++, vectors can also be initialized like this:

int arr[] = { 10, 20, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> vect(arr, arr + n);

Note

For anyone super involved: C++ only mandates a sorting method that has an O(n log(n)) worst case. Typically, however, “Introsort” is used, which is a hybrid sort that uses Quicksort, then switches to Heapsort to avoid the O(n^2) worst case of Quicksort. This sort is “unstable”. The stable sort is stable_sort(array);, which is typically a Merge sort.

In C#, as long as you have the import statements at the top for arrays and lists, the implementation is simple. For a standard array, the sort method is in the “Array” class:

Array.sort(array);

Where “array” is your array and “Array” is the class. For vectors, there is an internal method:

vector.sort()

Where “vector” is your vector.

Console.Write outputs without making another line at the end, and another line can be made by passing "\n" to it. Notice the backslash, "\" not "/".

Note

For anyone super involved: For both of these, C# uses a different algorithm depending on the number of items in the array. For less than 16, it uses Insertion sort. For a higher threshold, it uses Heapsort. For anything larger, it uses Quicksort. In other words, it’s better not to reverse a large array with this method because of Quicksort’s O(n^2) worst case. This sort is “unstable”, the “stable” sort is under Enumerable.OrderBy(someType); which is still a Quicksort, but a stable one.

The sorting methods are included in the import statement import java.util.*;. For a standard array, a member in the “Arrays” class is called with this syntax:

Arrays.sort(array);

Where array is your array. For “List” types, including “ArrayList”, a member of the “Collections” class is used:

Collections.sort(arrayList);

Where arrayList is your List variable.

Note

For anyone super involved: Anything later than and including Java 7 uses “Timsort”, the hybrid sort made for Python. Timsort is a hybrid sort that uses Merge sort then switches to Insertion sort when the size of a sub-array is small enough. Time complexity is O(n log(n)), and it is “stable”.

The syntax array.sort(); is used where array is your array variable.

Note

For anyone super involved: The sorting method used changes with types and browser. Usually, it can be assumed that an O(n log(N)) method is used, however that is not guaranteed, along with whether or not the sort is “stable”. JavaScript, as mainly a browser language, should not be used to sort massive datasets anyways, to the point where this would matter.

The syntax array.sort() is used where array is your array variable.

Note

For anyone super involved: Python uses “Timsort”, a sort by one of Python’s makers. Timsort is a hybrid sort that uses Merge sort, then switches over to Insertion sort when a given sub-array is small enough. Time complexity is O(n * log(n)), and it is “stable”.

The syntax array.sort() is used where array is your array variable.

Note

For anyone super involved: Swift used to use “Introsort”, a hybrid sort that uses Quicksort then switches over to Heapsort when a certain recursion depth is reached to avoid Quicksort’s O(n^2) worst case. Time complexity is O(n log(n)) and it is “unstable”.

Swift currently, as of 2019, uses “Timsort”, a hybrid sort between Mergesort and Insertion sort. The time complexity is O(n log(n)), and it is “stable”. The method is not “guaranteed” stable, however, which means Swift may switch to an unstable sort again in the future. Check with your swift version if this matters.