Counting Sort in java

Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times.
Basic idea of counting sort to find number of elements less than X, so X can be put to its correct position.

Steps for Counting Sort:

• Take an array to store count of each elements. Lets say array elements contain 1 to K then initialize count array with K.
• Now add elements of count array, so each elements store summation of its previous elements.
• Modified count array stores position of elements in actual sorted array.
• Iterate over array and put element in correct sequence based on modified count array and reduce the count by 1.

package org.arpit.java2blog;

import java.util.Arrays;

public class CountingSortMain {

 public static void main(String[] args) {
 System.out.println("Before Sorting : ");
 int arr[]={1,4,7,3,4,5,6,3,4,8,6,4,4};
 System.out.println(Arrays.toString(arr));
 arr=countingSort(arr);
 System.out.println("=======================");
 System.out.println("After Sorting : ");
 System.out.println(Arrays.toString(arr));
 }

 static int[] countingSort(int arr[])
 {
 int n = arr.length;

 // The result will store sorted array
 int result[] = new int[n];

 // Initialize count array with 9 as array contains elements from range 1 to 8.
 int count[] = new int[9];
 for (int i=0; i<9; ++i)
 count[i] = 0;

 // store count of each element in count array
 for (int i=0; i
When you run above program, you will get below output:
Before Sorting : 
[1, 4, 7, 3, 4, 5, 6, 3, 4, 8, 6, 4, 4]
=======================
After Sorting : 
[1, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8]
Time Complexity= O(N)
I would suggest to try to debug the program to understand it better.