### Merge Sort Algorithm

This algorithm is very efficient one, and is classic example of Divide and…

July 16, 2019

Counting sort runs on relatively smaller set of input.
Counting sort calculates, for every element in array - X, the number of elements which are lesser than - X. It then use this information to put *X* directly into its position in sorted array.

Selection sort takes two additional array.

- One for result, the sorted array
- other for temporary storage, where size equals to the maximum number on input array.

Its interesting to note that this algorithm is not a comparison sort. You will not see any comparison in code. This algorithm uses elements values to index into array.

- First iterate on input array, and calculate each number occurence in the 2nd additional array (lets call it C).
- After the iteration, The array-C’s index will denote the input number, and the value contains how many times the number comes in original array. In the image above, see part-a.
- Run one more iteration on array-c. And, accumulate the sum. See above image, part-b
- Now iterate equal to length of original array (from last index to 0):
- For the number in original array, use it as index in array-C, which will give you its position in sorted array
- Put this number in sorted array at position told by array-c
- Decrement this value from array-c by 1

- At the end, we will get sorted array.

See the code here:

```
public class CountSort {
private int[] arr;
public CountSort(int[] arr) {
this.arr = arr;
}
/**
* Count sort, max value-k
* @param k, the max value in array
*/
public int[] doSort(int k) {
int[] c = new int[k+1];
//count number of occurence
for (int i=0; i<this.arr.length; i++) {
c[this.arr[i]] ++;
}
//accumulate
for (int i=1; i<c.length; i++) {
c[i] += c[i-1];
}
int[] result = new int[this.arr.length];
//put the number to its designated place
for (int i=this.arr.length-1; i>=0; i--) {
result[c[this.arr[i]]-1] = this.arr[i];
c[this.arr[i]] --;
}
return result;
}
}
```

- It is not a comparison sort.
- It is a stable sort.
- This uses 2 additional arrays.
- It is used for relatively smaller set of numbers.
- The maximum number in array should be order of size of array. Example: this algorithm is good for sorting age of people.
- Performance is very good. its time complexity is
*O(n + k) ~= O(n)*

The algorithm runs on time complexity of *O(n + k) ~= O(n)* in worst/average case.

This algorithm is very efficient one, and is classic example of Divide and…

Problem Statement Given an array, rotate the array to the right by k steps…

Problem Statement You are given an array prices where prices[i] is the price of…

Max Priority Queue is a data structure which manage a list of keys(values). And…

Problem Statement Given a string, find the length of the longest substring…

Problem Statement Given a sorted array nums, remove the duplicates in-place such…

Introduction So you have a Django project, and want to run it using docker image…

Introduction It is very important to introduce few process so that your code and…

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…

Introduction We often require to execute in timed manner, i.e. to specify a max…

Introduction In some of the cases, we need to specify namespace name along with…

Introduction In most of cases, you are not pulling images from docker hub public…