$//$using the radix sort algorithm to sort strings that contain lowercase letters.

void radixSort$($LL& all$)$

$\{$

$//$Each slot of the buckets array is a LL object.

const int ALPHABET $=26$;

LL buckets$[$ALPHABET$]$; $//$bucket$[0]$ is for $\text{'}$a$\text{'}.$ There are $26$ buckets.

$//$ Start measuring time

double startTime $=$ getCurrentTimeMillis$()$;

$//$checking each place

for $($int place $=2$; place $>=0$; $--$place$)\{$

while $(!$all.empty$())\{$

$//$ pop the front node

Node$*$ poppedNode $=$ all.pop$()$;

$//$ calculate the index of the bucket based on the current place

int index $=$ poppedNode$->$getElem$()[$place$]-\text{'}$a$\text{'}$;

$//$ like shown in class

$//$ add the popped node to the end of the correct bucket

buckets$[$index$].$addRear$($poppedNode$)$;

$\}$

$//$keep on popping the front node and add it to the end of the correct bucket depending on the letter at the current place

$//$Once all the nodes of the all list are moved to the correct buckets, put them together by calling combineLists$().$

combineLists$($all$,$ buckets, ALPHABET$)$;

$\}$

$//$ End measuring time

double endTime $=$ getCurrentTimeMillis$()$;

double elapsedTime $=$ endTime $-$ startTime;

cout $$ "Time taken for sorting: $"$ elapsedTime milliseconds" $$ endl;

$//$For debugging, checkBuckets$()$ displays the contents of all the buckets

$//$ printLL$()$ displays all the elements in the list

checkBuckets$($buckets$,$ ALPHABET$)$;

$\}$Radix Sort

Algorithm

Best Time complexity

Worst Time complexity

Space Complexity for our implementation

Space complexity using counting sort

In$-$place for our implementation?

In$-$place using counting sort?

Stable?