15,901,205 members
Articles / General Programming / Performance

# Comparison of Sorting Algorithms

Rate me:
19 Jul 2021CPOL7 min read 34.2K   6   7
Comparison of the various sorting algorithms on the basis of several factors
The article provides a comprehensive comparison of sorting algorithms based on factors such as time complexity, space complexity, stability, and performance through field tests, aiming to guide readers in understanding each algorithm's strengths, weaknesses, and suitability for various scenarios.

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.

Sorting Algorithm Average Case Best Case Worst Case
Bubble Sort O(n2) O(n) O(n2)
Insertion Sort O(n2) O(n) O(n2)
Selection Sort O(n2) O(n2) O(n2)
Quick Sort O(n.log(n)) O(n.log(n)) O(n2)
Merge Sort O(n.log(n)) O(n.log(n)) O(n.log(n))
Heap Sort O(n.log(n)) O(n.log(n)) O(n.log(n))
Counting Sort O(n+k) O(n+k) O(n+k)
Bucket Sort O(n+k) O(n+k) O(n2)

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(n2) 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).

Sorting Algorithm Space Complexity
Bubble Sort O(1)
Insertion Sort O(1)
Selection Sort O(1)
Quick Sort O(log(n))
Merge Sort O(n)
Heap Sort O(1)
Counting Sort O(k)
Bucket Sort O(n)

### 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.

Sorting Algorithm Stable Sort?
Bubble Sort Yes
Insertion Sort Yes
Selection Sort No
Quick Sort No
Merge Sort Yes
Heap Sort No
Counting Sort Yes
Bucket Sort Yes

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.

Python
```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.

 Sorting Algorithm Test 1 (100) Test 2 (1000) Test 3 (10000) Bubble Sort Min: 0.01008 seconds Max: 0.0206 seconds Min: 1.0242 seconds Max: 1.0558 seconds Min: 100.922 seconds Max: 102.475 seconds Insertion Sort Min: 0.00306 seconds Max: 0.00650 seconds Min: 0.0369 seconds Max: 0.0562 seconds Min: 100.422 seconds Max: 102.344 seconds Selection Sort Min: 0.00556 seconds Max: 0.00946 seconds Min: 0.4740 seconds Max: 0.4842 seconds Min: 40.831 seconds Max: 41.218 seconds Quick Sort Min: 0.00482 seconds Max: 0.01141 seconds Min: 0.0370 seconds Max: 0.0383 seconds Min: 0.401 seconds Max: 0.420 seconds Merge Sort Min: 0.00444 seconds Max: 0.00460 seconds Min: 0.0561 seconds Max: 0.0578 seconds Min: 0.707 seconds Max: 0.726 seconds Heap Sort Min: 0.00489 seconds Max: 0.00510 seconds Min: 0.0704 seconds Max: 0.0747 seconds Min: 0.928 seconds Max: 0.949 seconds Counting Sort Min: 0.01929 seconds Max: 0.02052 seconds Min: 0.0354 seconds Max: 0.0400 seconds Min: 0.195 seconds Max: 0.203 seconds Radix Sort Min: 0.00315 seconds Max: 0.00394 seconds Min: 0.0294 seconds Max: 0.0309 seconds Min: 0.313 seconds Max: 0.338 seconds Bucket Sort Min: 0.00225 seconds Max: 0.00241 seconds Min: 0.0335 seconds Max: 0.0369 seconds Min: 1.854 seconds Max: 1.892 seconds

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

#### Observations

1. The O(n2) 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(n2) Algorithms were faster than the O(n.log(n)) Algorithms.
3. With every 10x increase in the amount of numbers, the O(n2) 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.

 Sorting Algorithm Sorted Data (1000) Bubble Sort Min: 0.542 seconds Max: 0.556 seconds Insertion Sort Min: 0.790 seconds Max: 0.821 seconds Selection Sort Min: 0.434 seconds Max: 0.464 seconds Quick Sort Min: 0.812 seconds Max: 0.872 seconds Merge Sort Min: 0.0289 seconds Max: 0.0364 seconds Heap Sort Min: 0.0604 seconds Max: 0.0661 seconds Counting Sort Min: 0.0055 seconds Max: 0.0124 seconds Radix Sort Min: 0.0119 seconds Max: 0.0145 seconds Bucket Sort Min: 0.0183 seconds Max: 0.0247 seconds

#### 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.

Written By
United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 Bubble Sort Jai Holloway10-Feb-23 5:58 Jai Holloway 10-Feb-23 5:58
 Bad testing Member 1159380820-Jul-21 9:33 Member 11593808 20-Jul-21 9:33
 Plagiarized ? Patrice T20-Jul-21 8:25 Patrice T 20-Jul-21 8:25
 Re: Plagiarized ? The Sun God20-Jul-21 22:39 The Sun God 20-Jul-21 22:39
 My vote of 5 Ștefan-Mihai MOGA20-Jul-21 1:17 Ștefan-Mihai MOGA 20-Jul-21 1:17
 There's also this Marc Clifton19-Jul-21 7:58 Marc Clifton 19-Jul-21 7:58
 Re: There's also this Mark Monnin24-Nov-21 3:17 Mark Monnin 24-Nov-21 3:17
 Last Visit: 31-Dec-99 18:00     Last Update: 19-May-24 4:08 Refresh 1