Key Metrics of Sorting Algorithms

labuladongOriginalAbout 528 words

Prerequisite Knowledge

Before reading this article, you should first learn:

During coding practice or interviews, you typically won't be asked to manually write sorting algorithms from scratch. However, for the sake of completeness, I have included a section that explains the principles, characteristics, time complexity, and code implementation of several common sorting algorithms using the visualization panel.

This article will first introduce several key metrics of sorting algorithms. When discussing specific sorting algorithms later, we will analyze them based on these metrics.

Time and Space Complexity

The first key metric is definitely time complexity and space complexity.

As mentioned in Introduction to Time and Space Complexity, for any algorithm, the smaller the time complexity and space complexity, the better.

Sorting Stability

Stability is an important property of sorting algorithms, which can be summarized as:

If the relative positions of identical elements remain unchanged after sorting, the sorting algorithm is considered "stable"; otherwise, it is "unstable".

For simply sorting an array of integers, stability might not be significant. However, when sorting more complex data structures, stable sorting can provide advantages.

For example, if you have several order records already sorted by transaction date, and you want to sort them by user ID, stable sorting will ensure that orders with the same user ID remain in order by their transaction date. This is the key difference between stable and unstable sorting:

If you use a stable sorting algorithm, after sorting, orders with the same user ID will still be arranged by transaction date:

   Date    UserID
2020-02-01  1001
2020-02-02  1001
2020-02-03  1001

2020-01-01  1002
2020-01-02  1002
2020-01-03  1002
...

Since the orders are already sorted by date, using a stable sorting algorithm ensures that the relative order of orders with the same user ID remains unchanged, keeping the date order intact.

If you use an unstable sorting algorithm, the relative order of orders with the same user ID may change, causing the date order to be lost for those orders.

As you can see, stability is a very important property. You should pay special attention when using sorting algorithms to avoid unexpected results.

In-Place Sorting

In-place sorting means performing the sort without requiring additional auxiliary space, using only a constant amount of extra space, and sorting directly on the original array.

Note, the key is whether additional space is needed, not whether a new array is returned. Specifically, it refers to differences like these:

// non-in-place sorting
void sort(int[] nums) {
    // requires an additional auxiliary array during sorting, consuming O(N) space
    int[] tmp = new int[nums.length];

    // sort the nums array
    for ...
}

// in-place sorting
void sort(int[] nums) {
    // directly operate on nums, no additional auxiliary array needed, consuming O(1) space
    for ...
}

It's easy to see that for sorting large data sets, in-place sorting algorithms have certain advantages.

Some key metrics for sorting algorithms are important to consider. Later, I will introduce several common sorting algorithms and analyze their strengths and weaknesses based on these metrics.