Heap Sort is one of the efficient sorting algorithms with a guaranteed worst case running time of O(NlogN). This is an in place sorting algorithm but it does not offer stable sorting.
In place Sorting: A sorting algorithm which sorts the input using very small or no extra space. It means that the input data is overwritten by the resulting output data.
Stable Sorting: A stable sorting algorithm is one, in which the relative order of equal keys is preserved. It means if there are non unique keys in the input data, then their relative order of occurrence in the input as well as output rem...

Read More
# Sorting

This category contains all the posts related to Sorting algorithms. This is a child to the category ‘Algorithms’.

## Comb Sort – An extension over the Bubble Sort

Introduction
This article is in continuation of the article Improving Bubble Sort – A detailed explanation which I wrote to explain the basic idea behind bubble sort.
Purpose of the article
This is an improvement over Bubble Sort, an improvement which is pretty much similar to Shell Sort over Insertion Sort. To know more about the relationship between Shell Sort and Insertion Sort, please read the articles in my previous posts.
What are we trying to improve?
Before we try to improve, we must know what to improve. The thing which is clear is that Bubble sort takes more time (or may I say m...

Read More
## Improving Bubble Sort – A detailed explanation

Introduction
Ever wondered why bubble sort is slow? Does it look similar to Insertion Sort ? Can it be improved to have better than quadratic time in average cases?
Here we start with a detailed analysis of bubble sort in the easiest possible way. Bubble Sort as the name suggests, bubbles up the heaviest (or may be lightest, depending on the comparison operator) elements to the top.
Purpose of the article
The article Improving Bubble Sort, is dedicated to explain the mechanism behind bubble sort in detail, apart from that, it also offers an improved bubble sort. Moreover, it also helps us ...

Read More
## Merge Sort

Introduction
Can sorting be made faster? We have seen sorting techniques like (Insertion Sort, Selection Sort and Shell Sort) which have a quadratic running time. With growing size of the inputs, it becomes tough to use these algorithms. Is there any faster alternative? We would like to find answers to these questions in the Merge Sort article.
On the other hand if you are interested in watching a video for this article, you can subscribe our Youtube Channel.
Purpose of the Article
In this article we try to answer the questions mentioned above. Yes there are many faster alternatives....

Read More
## How selection sort works – A detailed explanation

Introduction
Probably the most crude sorting technique, and also the most in-efficient one. But it's important, because until we know the worst we can't understand the importance of the good and the better. So let us try to find out, how selection sort works.
Purpose of the article
We will try to understand here, how selection sort works and how is the nature of input affecting the running time of this algorithm. Why this is a crude way of sorting and its advantages and dis-advantages.
Idea behind Selection Sort
As the name suggests, there is definitely something to select. Lets assume we...

Read More
## Basics of Shell Sort

Introduction
This article can be considered as the continutation of the article explaining Insertion Sort. To have a quick look please visit Insertion Sort. In this article we will learn how to over come the limitations of Insertion Sort by understanding the Basics of Shell Sort. You can also consider Shell Sort to be an improvement over Insertion Sort.
Purpose of the article
To understand the Basics of Shell Sort and compare it with insertion sort. We will also write code snippets and pseudo codes to understand it better.
Idea behind Shell Sort
The biggest limitation of Insertion Sort i...

Read More
## Easy way to understand quick sort

Introduction
This article touches in detail all the aspects of a quick sort algorithm. I tried to write it as simple as possible to make it an easy way to understand quick sort. This is really an interesting algorithm to learn and I have found that most of the students or professionals feel it hard to understand or re-produce in code.
Problem Statement
You are given an array A[a1,a2,a3, . . . . . . , an] having elements in a random order and we need to re-produce the array A[b1, b2, b3, . . . . , bn] where b1 < b2 < b3 < b4 < . . . < bn .
Basic idea behind quick sort
The ba...

Read More