Merge Sort

This is an algorithm based on the divide and conquer principle. The algorithm divides the problem of sorting an array into smaller problems of sorting smaller arrays. These smaller sorted arrays are then merged into bigger sorted arrays in the conquer phase until we have a completely sorted array.

Time Complexity: O(nlogn) - From the recurrence tree of this algorithm, there are atmost logn levels of this binary tree. The cost of merging the small sorted arrays is n at each level, thus nlogn.

Space Complexity: O(nlogn)

Selection Sort

One of the simplest sorting algorithms to implement. The idea is to select the smallest element from the unsorted array and place it in its right position. With every iteration, the unsorted array gets shorter until there is no element to place in its correct position.

Time Complexity: O(n^2)
Space Complexity: O(1)

Insertion Sort

This is an insanely inefficient but simple to implement sorting algorithm. The analogy for this algorithm can be drawn from the card game. Imagine the cards lying face down on the table. You pick cards one by one from the table and arrange them in a sorted order in your hand. For every card after the second card picked, put that card in its right place by comparing that card with the cards in your hand from right to left.

Time Complexity: Average and Worst Case is O(n^2)

                 Best Case is O(n)

Space Complexity: O(1)