Sorting Algorithms – Use and Efficiency

Very good. Today I was at my company working when I heard briefly about organizing large databases and the time that this task can take, and I asked myself "What are the best algorithms for sorting large amounts of data?«. That is why today I bring you an article about some of the most popular sorting algorithms, with their use, performance, and memory consumption.

Best Data Sorting Algorithms

Bubble Sort

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Bubble	Exchange	n^2	n^2	n^2	1

This sorting algorithm works as follows: It goes through a list always comparing one element and the next. If they are not in the desired order, flip them over and continue with the next items on the list. This process is repeated as many times as there are elements in the list.

The Bubble Sort algorithm is one of the simplest that exists, with a fairly intuitive implementation and a performance of n^2. This means that it may have decent performance for small groups of elements, but it will not be effective in the case of having a large group of elements to sort, because the time it will take to sort the set will increase exponentially. A curious fact about this sorting algorithm is that it is the slowest of all in sorting a list of elements that is already sorted. For this reason It is considered one of the most inefficient algorithms of all, and is only used in programming classes to introduce these algorithms, due to its simplicity.

Quick Sort

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Fast	Partition	n * log(n)	n * log(n)	n^2	log n

This sorting algorithm works as follows: An item is randomly selected from the list and used as a divider. All elements to the right and left will then be sorted, thus creating two new sublists. In each of these sublists we repeat the process until sublists with a single element are created. When all sublists have only one element, execution stops.

Although in the GIF shown above it seems like a complicated and slow process, it is actually the best algorithm for sorting giant sets of data, since thanks to its implementation the time it takes to sort a list increases logarithmically, and not constantly. or exponentiation as occurs in other cases. Furthermore, in most cases, a selection algorithm is usually applied first to decide quite accurately what the initial pivot or divisor will be, helping to get closer to its optimal performance than to its performance in the worst case. Another point that is very much in favor of Quick Sort compared to other n * log(n) performance algorithms is that this is the one that performs the least unnecessary exchanges of elements. That makes it the optimal algorithm for sorting gigantic lists of data.

Merge Sort

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Mix	Mix	n * log(n)	n * log(n)	n * log(n)	n

How does this algorithm work?

This sorting algorithm works as follows: First you divide every list of elements into lists of a single element. You put those lists back together to create two-item lists, and you sort them. After those lists you always compare the first element, and move them in order to a list of four elements. You repeat the process again with lists of eight elements, and so on until you once again have a single list, which will now be ordered.

Merge sort is also one of the most effective when dealing with very very large groups of elements, and can be superior to the Quick Sort algorithm if we do not choose the pivot of the latter well. Even so, its memory consumption is greater, and applying a second algorithm to correctly choose the pivot in Quick Sort does not cost as much as the memory consumption of this algorithm.

Insertion Sort

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Bubble	Insertion	n	n^2	n^2	1

How does this algorithm work?

This sorting algorithm works as follows: Start by creating a new list and remove the first element from the initial list to add it to the new one. It then extracts the second element from the initial list and inserts it into the new one in an orderly manner, always comparing from right to left. With the third and the rest of the elements it behaves exactly the same, until the initial list is empty.

This type of sorting algorithm is especially useful for small groups of elements, since although its average performance is n^2, it benefits greatly from elements that already have a certain order in the initial list. In this way, its average performance can be modified depending on the initial state of the elements, and in small groups it is not difficult for its performance to be closer to an * log(n) than to an^2.

Sort by Selection

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Selection	Selection	n^2	n^2	n^2	1

How does this algorithm work?

This sorting algorithm works as follows: The entire list of elements is traversed and the smallest one that has been found is always saved. If as you go through the list you find one smaller than the one you found before, you replace the old one with the new one. When you reach the end of the list, you take that element to the first position, and you start going through the list again but from the second element. Like this until it's your turn to start scrolling through the list from the last element.

This algorithm is also most effective when it has to sort small groups of elements. Still, its only advantage over the insertion algorithm is that it is written with less code and is more intuitive for humans. In this way, and not being able to offer better performance than insertion sort, this algorithm is usually relegated to second place, and is very rarely used professionally.

Arrangement by Mounds

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Mounds	Selection	n * log(n)	n * log(n)	n * log(n)	1

This sorting algorithm works as follows: You select the first item in the list and save two spaces for the second and third items. If any of these elements are larger than the parent, you swap them. Then in each of those child elements you save two other numbers from the list, and if any of those numbers are larger than the parent, you swap them until no parent element is smaller than one child. You repeat this process until you reach the last item on the list.

Then you break down this tree of lists that you have created, and you order the elements from top to bottom, without having to review any of the elements that you have ordered once you go down to the next level of the tree.

Although it is very rare to implement, mathematically speaking it is the most efficient algorithm of all. However, although it can compete on par with Merge Sort, it usually falls short of Quick Sort, since the latter hardly performs unnecessary data exchanges, and it is a very valuable time that is saved.

Radix Ordering

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Radix	Non-Comparative	n*k	n*k	n*k	n

This sorting algorithm works as follows: Any value in the list is transformed into a number, and for each number in the list, you compare the digit on the right, and create groups based on its value. Then, from those groups you compare the second digit from the right (if it does not exist, you create it as a 0), and you create groups again and order them according to their value and the group to which they belonged. This process is repeated until no number has more digits to the right.

Although mathematically speaking the performance of this algorithm may be better than any other on this list, the reality is that the constant (k), which represents the maximum number of digits in a number in the list, and with which its Performance is usually much greater than log(n), in addition to its excessive memory consumption.

Sorting by Boxes

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Lockers	Non-Comparative	n	n + (n^2 / k) + k	n^2	n

This sorting algorithm works as follows: It works similar to Radix Sort, since you start by grouping all the elements in the list according to different groups. Then each group is ordered with one or several extra algorithms, and in this way you ensure that these last algorithms do not become so overloaded.

Sorting by Accounts

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Accounts	Non-Comparative	n+k	n+k	n+k	n + k

This sorting algorithm works as follows: Scrolls through the list of elements (only supports integers) to select the largest and smallest. Then it creates groups for each number between the largest and the smallest, and when it goes through the list again the only thing it does is move each element to its corresponding group (there is a group for each number).

It is not an efficient algorithm if there are numbers with a large difference in size, but it is usually used as a sub-routine in algorithms such as Radix or Sort by Counts because these two algorithms create smaller groups and in this way greatly reduce the size difference between numbers.

In addition, it is also a really effective algorithm for sorting very large groups of data in which the largest data is much smaller than the total number of elements in the list.

Other Ineffective Algorithms

Stupid Ordering

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Idiot	?	n	nxn!	It does not finish	1

This sorting algorithm works as follows: First, it checks if the list of elements is ordered, and if it is, the entire list of elements is reordered randomly and starts again.

Ordering Pancakes / Pancakes

Algorithm	Method	Better performance	Average Performance	Worst Performance	Memory
Pancakes / Pancakes	?	n	n^2	n^2	1

This sorting algorithm works as follows: You go through the list of elements to see which is the largest, and from the first element to that, you reverse the order of all the elements, so that the largest is at the top. Then you reverse the order of all the elements in the list, so that the largest is at the bottom. You then repeat this process until there are no items left to flip.

Summary of the best algorithms according to their performance

Although there is no definitive algorithm to order a list of elements, it is true that not all of them have the same performance depending on the cases they face. In this way, there are algorithms that shine for specific cases, and others that do so in a general way, such as Quick Sort when it comes to sorting gigantic groups of data, or Insertion Sort when it comes to sorting groups of data of a large size. relatively small.

Algorithm Name	Better performance	Average Performance	Worst Performance	Memory
Quick Sort	Ω (n * log(n))	Θ (n * log(n))	O(n^2)	Or (log n)
Bubble Sort	Ω (n)	Θ(n^2)	O(n^2)	Or (1)
Merge Sort	Ω (n * log(n))	Θ (n * log(n))	O (n * log(n))	O(n)
Insertion Sort	Ω (n)	Θ(n^2)	O(n^2)	Or (1)
Sort by Selection	Ω(n^2)	Θ(n^2)	O(n^2)	Or (1)
Arrangement by Mounds	Ω (n * log(n))	Θ (n * log(n))	O (n * log(n))	Or (1)
Radix Ordering	Ω(n*k)	Θ(n*k)	O(n*k)	O(n)
Sorting by Boxes	Ω(n+k)	Θ(n+k)	O(n^2)	O(n)
Sorting by Accounts	Ω(n+k)	Θ(n+k)	O(n+k)	O(n+k)
Stupid Ordering	Ω (n)	Θ (nxn!)	O (∞) Infinity	Or (1)
Pancake / Pancake Arrangement	Ω (n)	Θ(n^2)	O(n^2)	Or (1)