Understanding sorting algorithms is a must for software engineers. This topic is also common in a programming interview. There is a lot of sorting algorithms out there, and I want to cover some of them here. I also gave some examples in C.

Selection Sort

Select and compare an element with other elements at each iteration. The complexity of Selection Sort is O(n^{2}).

Bubble Sort

Select and compare an element with its neighbor then swap if it is not in order. The complexity of Bubble Sort is O(n^{2}).

Insertion Sort

Similar to Bubble Sort. It inserts the next element into the sorted sublist. The complexity of Insertion Sort is O(n^{2}).

Shell Sort

Shell Sort partitions the list into sublists where a sublist is elements that are separated by a gap. The gap keeps reducing the value until it becomes one. Each sublist is sorted using Insertion Sort. The complexity of Shell Sort is O(n^{2}).

Merge Sort

Merge Sort is a Divide and Conquer algorithm. Divide the unsorted list into sublists then repeatedly merge sublists to produce new sorted list. The complexity of Merge Sort is O(n log n).

Quick Sort

Quick Sort is similar to Merge Sort. It is a Divide and Conquer algorithm. It partitions the list at every step based on a pivot. The complexity of Quick Sort is O(n log n).

Conclusion

It is also important to understand Big-O notation, to understand the time complexity of an algorithm. Most of them are O(n^{2}). But some recursive sorts such as Merge and Quick Sort have O(n log n). There is still a lot of sorting algorithms that I didn't cover here. But these are the famous ones.

There is a question that asks you to sort in some programming interview. Whatever the sorting algorithm that you choose is up to you. I prefer the Insertion or Merge Sort.