Usually, the sorting algorithms determine the sort based on comparisons between the input elements. That is why they called comparison sorts algorithms. In here we would like to consider non-comparison sorts.

Algorithm is any well-defined computational procedure that takes some value, or set of values as input and produces some value, or set of values, as output.

The quicksort algorithm has a worst-case running time of O(n^2) on an input array of n numbers, and worst case happens when the array is sorted in descending order. Despite a worst-case running time, quicksort is often the best practical choice for sorting. Its average expected running time is O(n log n), and it has an advantage of sorting in place.

Merge sort is another sorting algorithm that applies the divide-and-conquer approach, where the problem is divided into sub-problems recursively. Keep dividing until the subproblem becomes primitive. After that, the results of the divisions are combined and formed the result for the upper caller and so on.

The i th *order statistic of a set of n elements is the i th smallest element. Simply saying the minimum of a set of elements is the first order statistic (i = 1) and maximum is the nth order statistic (i = n). Median is the informally considered as a “halfway point” of the set.

Insertion sort, which is an efficient algorithm for sorting a small number of elements. Insertion sort works the way many people do it by hand while playing a card game (Though personally i would not sort the cards while playing, because there are too many skill-full guys, who may take an advantage of it)

The (binary) heap data structure is an array object that we can view as a nearly complete binary tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

In a paradigm of divide-and-conquer we solve the problem recursively, applying three basic steps at each level of the recursion:

It has been such a long time since I didn’t work on graphs and trees. Here it is I’m back. This task is quite a simple one even though it is assigned a medium level of difficulty. The original task definition is given hackerrank.