Counting Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Counting Sort Algorithm

Find max value in array

↓

Create count array of size max+1

↓

Initialize count array with zeros

↓

Count each element's frequency

↓

Modify count array to store positions

↓

Build output array using count positions

↓

Copy output array back to original

↓

Sorted array ready

Counting Sort counts how many times each number appears, then uses that to place numbers in order.

Execution Sample

DSA Javascript

const arr = [4,2,2,8,3,3,1];
const max = 8;
const count = new Array(max+1).fill(0);
// Count frequencies
for (let num of arr) count[num]++;
// Modify count
for (let i=1; i<=max; i++) count[i]+=count[i-1];
// Build output
const output = new Array(arr.length);
for (let i=arr.length-1; i>=0; i--) {
  output[--count[arr[i]]] = arr[i];
}
// Copy output to original array
for(let i=0; i<arr.length; i++) {
  arr[i] = output[i];
}

This code sorts the array using counting sort by counting frequencies and placing elements in order.

Execution Table

Step	Operation	Array State	Count Array State	Output Array State	Pointer/Index Changes	Visual State
1	Initial array	[4, 2, 2, 8, 3, 3, 1]	[0,0,0,0,0,0,0,0,0]	[]	count initialized to zeros	arr: 4,2,2,8,3,3,1; count: all zeros; output: empty
2	Count frequencies	[4, 2, 2, 8, 3, 3, 1]	[0,1,2,2,1,0,0,0,1]	[]	count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1	count updated with frequencies of each number
3	Modify count to positions	[4, 2, 2, 8, 3, 3, 1]	[0,1,3,5,6,6,6,6,7]	[]	count cumulative sums	count now shows positions for each number
4	Build output from right to left	[4, 2, 2, 8, 3, 3, 1]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	i moves from 6 to 0; count updated after placing each element	output filled in sorted order; count decremented for each placement
5	Copy output to original	[1, 2, 2, 3, 3, 4, 8]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	arr overwritten with output	arr is now sorted
6	End	[1, 2, 2, 3, 3, 4, 8]	[0,0,1,3,5,6,6,6,6]	[1,2,2,3,3,4,8]	Sorting complete	Final sorted array

💡 All elements placed in output; original array overwritten with sorted values

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
arr	[4,2,2,8,3,3,1]	[4,2,2,8,3,3,1]	[4,2,2,8,3,3,1]	[4,2,2,8,3,3,1]	[1,2,2,3,3,4,8]
count	[0,0,0,0,0,0,0,0,0]	[0,1,2,2,1,0,0,0,1]	[0,1,3,5,6,6,6,6,7]	[0,0,1,3,5,6,6,6,6]	[0,0,1,3,5,6,6,6,6]
output	[]	[]	[]	[1,2,2,3,3,4,8]	[1,2,2,3,3,4,8]
i	N/A	N/A	N/A	6 to 0	N/A

Key Moments - 3 Insights

Why do we modify the count array to store positions instead of just frequencies?

Modifying count to cumulative sums lets us know the exact position where each number should go in the output. See step 3 in execution_table where count changes from frequencies to positions.

Why do we build the output array from right to left?

Building from right to left keeps the sort stable by placing duplicates in correct order. Step 4 shows i moving from end to start, updating output and count accordingly.

What happens if the input array contains numbers outside the range of count array?

Counting sort requires knowing max value to size count array. If numbers exceed max, it causes errors or wrong results. Step 1 finds max to prevent this.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does the count array represent?

A Frequencies of each number

B Positions where each number should be placed

C Sorted output array

D Original input array

💡 Hint

Refer to the 'Count Array State' column at step 3 showing cumulative sums

At which step does the output array get fully filled with sorted elements?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Check 'Output Array State' column; step 4 shows output filled

If the input array had a number 9, what would need to change in the code?

A Increase max to at least 9 and size count array accordingly

B Decrease max to 8

C No change needed

D Remove number 9 from input

💡 Hint

See step 1 where max is found to size count array

Concept Snapshot

Counting Sort Algorithm:
- Find max value in array
- Create count array sized max+1, initialize zeros
- Count frequencies of each element
- Modify count to cumulative sums (positions)
- Build output array from right to left using count
- Copy output back to original array
- Stable and efficient for small range integers

Full Transcript

Counting Sort works by counting how many times each number appears in the input array. First, it finds the maximum number to know how big the count array should be. Then it creates a count array filled with zeros. Next, it counts the frequency of each number in the input and stores it in the count array. After that, it modifies the count array to hold cumulative sums, which represent the positions where each number should be placed in the output array. The algorithm then builds the output array by placing elements from the input array into their correct positions, moving from right to left to keep the sort stable. Finally, it copies the sorted output back into the original array. This method is very efficient for sorting integers within a small range.