Performance of sort functions in C++ and Java

In this article, we will first explore the sorting functions available in C++ and Java. And then, check using simple programs how long they take for 1 lakh and 10 lakh integer arrays.

The system configuration used for compiling and running the program is as below.

$ uname -a
Linux ip-172-31-0-61 5.19.0-1022-aws #23~22.04.1-Ubuntu SMP Fri Mar 17 15:38:24 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux

$ cat /etc/os-release 
PRETTY_NAME="Ubuntu 22.04.1 LTS"
NAME="Ubuntu"
VERSION_ID="22.04"
VERSION="22.04.1 LTS (Jammy Jellyfish)"
...
...

$ java -version
openjdk version "11.0.18" 2023-01-17
OpenJDK Runtime Environment (build 11.0.18+10-post-Ubuntu-0ubuntu122.04)
OpenJDK 64-Bit Server VM (build 11.0.18+10-post-Ubuntu-0ubuntu122.04, mixed mode, sharing)

$ g++ --version
g++ (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
...
...

Sorting algorithm functions in C++

In C++, the Standard Template Library (STL) provides a variety of sorting algorithms through its header files. Here are the most commonly used sorting functions:

sort(): This function is found in the <algorithm> header file and provides a fast and efficient way to sort a range of elements in a container. By default, it uses a comparison operator < to sort elements in ascending order.

#include <algorithm>
// ...
std::vector<int> v = {5, 2, 4, 1, 3};
std::sort(v.begin(), v.end());

stable_sort(): Also found in the <algorithm> header, this function sorts the elements in a stable manner, i.e., it maintains the relative order of elements with equal values. It’s generally slower than sort() but useful when the original order of equal elements must be preserved.

#include <algorithm>
// ...
std::vector<int> v = {5, 2, 4, 1, 3};
std::stable_sort(v.begin(), v.end());

partial_sort(): This function is found in the <algorithm> header and sorts a subrange of elements in a container, leaving the other elements unordered. It’s useful when you need only a few smallest or largest elements in the container.

#include <algorithm>
// ...
std::vector<int> v = {5, 2, 4, 1, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());

nth_element(): This function is found in the <algorithm> header and rearranges the elements in a container such that the element at the nth position is the one that would be in that position if the container were sorted. It also partitions the other elements such that those before the nth element are less than or equal to it, and those after the nth element are greater than or equal to it.

#include <algorithm>
// ...
std::vector<int> v = {5, 2, 4, 1, 3};
std::nth_element(v.begin(), v.begin() + 2, v.end());

Remember that you can also use custom comparison functions with these sorting algorithms to sort the elements based on specific conditions or in a different order (e.g., descending).

C++ program to measure time for sort functions

Here’s a simple C++ program demonstrating the use of the three sorting algorithms mentioned earlier. This program generates an array of 100,000 random integers and then sorts them using the three methods while measuring their execution time.

#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>
#include <random>

int main() {
    const int size = 1000000;
    std::vector<int> arr(size);
    std::random_device rd;
    std::mt19937 gen(rd());

    for (int i = 0; i < size; i++) {
        arr[i] = gen();
    }

    // std::sort()
    std::vector<int> arrCopy = arr;
    auto startTime = std::chrono::high_resolution_clock::now();
    std::sort(arrCopy.begin(), arrCopy.end());
    auto endTime = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> elapsedTime = endTime - startTime;
    std::cout << "std::sort() time: " << elapsedTime.count() << " ms" << std::endl;

    // std::stable_sort()
    arrCopy = arr;
    startTime = std::chrono::high_resolution_clock::now();
    std::stable_sort(arrCopy.begin(), arrCopy.end());
    endTime = std::chrono::high_resolution_clock::now();
    elapsedTime = endTime - startTime;
    std::cout << "std::stable_sort() time: " << elapsedTime.count() << " ms" << std::endl;

    // std::partial_sort()
    arrCopy = arr;
    startTime = std::chrono::high_resolution_clock::now();
    std::partial_sort(arrCopy.begin(), arrCopy.begin() + size / 2, arrCopy.end());
    endTime = std::chrono::high_resolution_clock::now();
    elapsedTime = endTime - startTime;
    std::cout << "std::partial_sort() time: " << elapsedTime.count() << " ms" << std::endl;

    return 0;
}

The program can be downloaded at https://github.com/codeversionmaster/cplusplus/blob/cplusplus17/projects/sorting_demo.cpp.

Below is the compilation and execution output.

//For 1 lakh array
$ g++ -o sorting_demo sorting_demo.cpp 
$ ./sorting_demo 
std::sort() time: 41.5864 ms
std::stable_sort() time: 49.3955 ms
std::partial_sort() time: 81.4008 ms

//For 10 lakh array
$ g++ -o sorting_demo sorting_demo.cpp 
$ ./sorting_demo 
std::sort() time: 488.42 ms
std::stable_sort() time: 609.185 ms
std::partial_sort() time: 1048.5 ms

Sorting algorithm functions in Java

In Java, you can use the following classes and methods to sort collections:

  1. Arrays.sort(): This method is part of the java.util.Arrays class and is used for sorting arrays of primitive types or objects. By default, it sorts elements in ascending order.
  2. Collections.sort(): This method is part of the java.util.Collections class and is used to sort instances of the List interface. By default, it sorts elements in ascending order.
  3. List.sort(): This method is part of the List interface (available since Java 8) and allows you to sort the elements of a list in place.
  4. Stream.sorted(): This method is part of the Stream API (available since Java 8) and is used for sorting elements in a stream. You can convert the sorted stream back to a collection after sorting.

You can also use custom comparators to define specific sorting orders or conditions for all these sorting methods. For example, you can use lambda expressions or implement the Comparator interface to create a custom comparator for your sorting needs.

Here’s a simple Java program that demonstrates using the four sorting methods mentioned earlier. This program generates an array of 100,000 random integers, creates lists, and then sorts them using the four methods while measuring their execution time.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

public class SortingDemo {
    public static void main(String[] args) {
        int size = 1000000;
        int[] arr = new int[size];
        Random random = new Random();

        for (int i = 0; i < size; i++) {
            arr[i] = random.nextInt();
        }

        // Arrays.sort()
        int[] arrCopy = Arrays.copyOf(arr, size);
        long startTime = System.currentTimeMillis();
        Arrays.sort(arrCopy);
        long endTime = System.currentTimeMillis();
        System.out.println("Arrays.sort() time: " + (endTime - startTime) + " ms");

        // Collections.sort()
        List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
        startTime = System.currentTimeMillis();
        Collections.sort(list);
        endTime = System.currentTimeMillis();
        System.out.println("Collections.sort() time: " + (endTime - startTime) + " ms");

        // List.sort()
        list = Arrays.stream(arr).boxed().collect(Collectors.toList());
        startTime = System.currentTimeMillis();
        list.sort(null);
        endTime = System.currentTimeMillis();
        System.out.println("List.sort() time: " + (endTime - startTime) + " ms");

        // Stream.sorted()
        list = Arrays.stream(arr).boxed().collect(Collectors.toList());
        startTime = System.currentTimeMillis();
        List<Integer> sortedList = list.stream().sorted().collect(Collectors.toList());
        endTime = System.currentTimeMillis();
        System.out.println("Stream.sorted() time: " + (endTime - startTime) + " ms");
    }
}

This program generates random integers, measures the time taken for each sorting method, and prints the results to the terminal. The actual times may vary depending on your system, the Java implementation, and the current workload.

The program can be downloaded at https://github.com/codeversionmaster/cplusplus/blob/cplusplus17/projects/SortingDemo.java.

Below is the compilation and execution output.

//For 1 lakh array
$ javac SortingDemo.java 
$ java SortingDemo 
Arrays.sort() time: 30 ms
Collections.sort() time: 121 ms
List.sort() time: 97 ms
Stream.sorted() time: 200 ms

//For 10 lakh array
$ javac SortingDemo.java 
$ java SortingDemo 
Arrays.sort() time: 294 ms
Collections.sort() time: 590 ms
List.sort() time: 341 ms
Stream.sorted() time: 610 ms

Conclusion

The summary of times of sort functions in C++ and Java is below.

Programming Language1 lakh integer array10 lakh integer array
C++std::sort() time: 41.5864
ms std::stable_sort() time: 49.3955 ms
std::partial_sort() time: 81.4008 ms		std::sort() time: 488.42 ms
std::stable_sort() time: 609.185 ms
std::partial_sort() time: 1048.5 ms
JavaArrays.sort() time: 30 ms
Collections.sort() time: 121 ms
List.sort() time: 97 ms
Stream.sorted() time: 200 ms 		Arrays.sort() time: 294 ms
Collections.sort() time: 590 ms
List.sort() time: 341 ms
Stream.sorted() time: 610 ms