In this article, we will compare different sorting algorithms. A table will be used to present the results. All the algorithms were implemented in Java.
| Algorithm | Best case | Average case | Worst case | Space complexity | Stable | Comparisons | Swaps | Time (ms) |
|---|---|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | 0.000000 | 0.000000 | 0.000000 |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | 0.000000 | 0.000000 | 0.000000 |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No | 0.000000 | 0.000000 | 0.000000 |
| Merge sort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) | Yes | 0.000000 | 0.000000 | 0.000000 |
| Quick sort | O(n log(n)) | O(n log(n)) | O(n^2) | O(log(n)) | No | 0.000000 | 0.000000 | 0.000000 |
| Heap sort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) | No | 0.000000 | 0.000000 | 0.000000 |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | 0.000000 | 0.000000 | 0.000000 |
-
The table will be updated as new algorithms are added.
-
Stable: When two or more elements have the same value, the algorithm does not change the order of the elements.
-
Comparisons: Refers to the total of comparisons made by the algorithm to sort the array.
-
Swaps: Refers to the total of swaps made by the algorithm to sort the array.
-
Time: Refers to the total time taken by the algorithm to sort the array.
-
All the algorithms were tested with the same array of ten thousand elements. The array was generated with random numbers. The tests were performed on a computer with the following specifications:
System Model: Nitro AN515-54 || Processor: Intel(R) Core(TM) i5-9300H CPU @ 2.40GHz, 2400 Mhz, 4 Core(s), 8 Logical Processor(s) || OS Name: Microsoft Windows 11 Home Single Language || Available Physical Memory: 7,93 GB