Comparison of Sorting Algorithms

Welcome to our Comparison on Sorting Algorithms article. Here, we'll be comparing the various sorting algorithms out there on the basis of several factors:

• Time Complexity
• Space Complexity
• Stable/Unstable
• Actual Fields Tests

We’ll top it all off by trying to describe where each Algorithm is best suited, and their strong and weak points. Every algorithm is unique, and performs best under certain circumstances unique to it.

Comparison of Time Complexity

A table that shows the time complexities for some of the most commonly used Sorting Algorithms. Time complexity is the first thing that you need to be checking when comparing two sorting algorithms. The lower the time complexity, the better.

We’ve used a color scheme in the table above, to help with our Comparison of Sorting Algorithms. Red is the worst, under which the O(n²) Algorithms lie. The O(n.log(n)) Algorithms are next, which are the middle ground. The best time complexity is O(n), which is the fastest an algorithm can be.

Later, when we do the actual field tests, you can use this table as reference. You will notice how much of an impact time complexity has on performance.

Comparison of Space Complexity

While speed is important and usually your top priority, sometimes in places with memory constraints, Algorithms with low memory costs are preferred.

The below table shows the Space Complexity for the various Sorting Algorithms. You might notice, that the Algorithms with higher space complexities are those which are “out of place” and the ones with the lowest, are in-place. This is of course, because Out of Place Algorithms create extra arrays to store the data in, while In-place uses the same array.

It goes without saying, that the best Space Complexity is O(1).

Stable and Unstable Algorithms

This is a rather niche use, and only makes an actual difference in certain types of data. However, it remains an important requirement that is needed for these certain scenarios.

Is it important to note however, that you can usually create stable versions of the above Algorithms. The ones being referred to in the image above, are the “Classic” versions of the Algorithm.

You can also check out our YouTube series on Sorting Algorithms!

Sorting Algorithms – Fields Tests

Finally, we are going to be measuring the main component, performance. We have tested the nine algorithms featured here under a variety of circumstances. From 100 numbers to 10,000 as well as tests using already sorted data, these tests will reveal quite a bit.

Testing Method

I’ve used Google Collab for running these tests, to ensure a constant and fair testing environment. To be clear, the code for these sorting algorithms was written in Python and written in a fairly standard manner. No heavy optimizations were applied, and only standard (classic) versions of the algorithms were used.

The Python timeit and random library were used to generate the random data, and perform continuous and repeated tests for each algorithm. This is again, to ensure fair results. The Random library is used to generate numbers from 1 to 10,000 and the timeit library performs each test 5 times in total, and returns a list of all 5 times. We’ve displayed both the max and min values for the 5 tests, so you can see the displacement of times.

Each one of the 5 tests is actually running the code 10 times, (the number parameter, default value 1,000,000). This increases the accuracy by doing a lot of tests and adding together the values to average it out. If you want the individual time for one single sort, divide the min/max value by 10. The number of repetitions is controlled by the repeat parameter (default value 5).

You can see the code for the testing function in the code below. If you follow the links for the timeit and random library, you can learn more about what’s going on here.

import random
import timeit
import sys

def test():
  SETUP_CODE = '''
from __main__ import sort
from random import randint'''
  
  TEST_CODE = '''
array = []
for x in range(1000):
  array.append(x)
sort(array)
  '''
  times = timeit.repeat( setup = SETUP_CODE,
                          stmt = TEST_CODE,  
                          number = 10,
                          repeat = 5) 

  print('Min Time: {}'.format(min(times)))
  print('Max Time: {}'.format(max(times)))

Sorting Algorithms – Performance Comparison

In this section, we are going to conduct three sets of tests. The first will have 100 random numbers, the second will have 1000 and the third will have 10,000. Take a good look at the table, compare the time complexities, and make your own observations. I’ll share my observations right after this.

I wanted to also include tests for 100,000 and 1,000,000 numbers, but the O(n²) Algorithms were taking forever to complete, so I gave up.

Observations

1. The O(n²) Algorithms (Bubble and Insertion Sort) reacted very poorly as the number of tests went up to 10,000. At 10,000 numbers the other Algorithms were on average, over 100x times faster.
2. On the test cases with just 100 numbers, the O(n²) Algorithms were faster than the O(n.log(n)) Algorithms.
3. With every 10x increase in the amount of numbers, the O(n²) Algorithms completion time increased by 100x.
4. Radix Sort and Counting Sort were on average, the fastest Algorithms.
5. Heapsort is fastest Algorithm with a space complexity of O(1).

Sorted Data Comparison

Another very interesting case is when Sorted Data is used, instead of random data. This test is mainly to show which Sorting Algorithms perform with sorted/partially sorted data and which perform worse.

Observations

1. Surprise, Surprise. Quick Sort Algorithm doesn’t live up to its name, and is the slowest out of all the above algorithms for a 1000 sorted numbers. This is because Quick Sort doesn’t respond well to degenerate cases like this, and requires special optimizations such as “randomized pivots”.
2. With the exception of Quick Sort, the time required dropped for all Algorithms.
3. Counting Sort performs the best, followed by Radix and Bucket Sort.

This marks the end of the Sorting Algorithms Comparison article. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can be asked in the comments section below.