Sorting algorithms - Questions and answers

Here are some good examples of the questions that we might be asked during the coding interview.

 Comparison of Sorting Algorithms - in-depth analysis

Let's go through and compare the five most famous algorithms, that we already covered in previous posts:

 Quick Sort

Intro

Quick sort is an efficient sorting algorithm, that is based on the divide and conquer approach.
Just like with the Merge sort, it divides the array into smaller sub-arrays and applies the solution to the smaller parts first.
It has a time complexity of O(n log n) - the same as Merge sort.

 Merge Sort

Intro

Merge sort is an efficient divide-and-conquer sorting algorithm that has a time complexity of O(n log n).

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems, until they become simple enough to be solved directly.

Insertion Sort

Intro

Insertion sort is one of the three famous algorithms (Bubble Sort, Selection Sort, and Insertion Sort) that have a time complexity of O(n^2), which means it is not a fast sorting algorithm.

Let's see how it works and its implementation.

 Selection sort

Intro

Selection sort fits into the group of the slowest sorting algorithms (together with Bubble sort and Insertion sort) with the time complexity of the O(n^2).

It is one of the slowest algorithms because we need to write nested loops, just like we did in the Bubble sort. 

Bubble Sort

Intro

Bubble sort - one of the slowest sorting algorithms. But let's see why.

It has a time complexity of O(n^2) (n squared). Why?
Because to implement it, we need to use a nested loop. It means we will have a loop inside another loop. That's because, in bubble sort, we need to compare one element with every (almost every) other element and swap them if necessary.