sort. However, since we set b $=128,$ b is a constant and the runtime is therefore O$($n$).$

Lab Assignment $6$

CS $302$ Advanced Data Structures and File Processing

Problem

You are given an array of non$-$negative integers, where different integers may have different numbers

of digits, but the total number of digits over all the integers in the array is n$.$ Show how to sort the

array in O$($n$)$ time$1.$

To implement this problem, we represent a single integer as array of bytes. Each byte represents a digit

$($base $128).$ The byte with index $0$ in the array represents the least significant byte. That is$,$ if A has

length $3,$ A$[0]=6,$ A$[1]=7,$ and A$[2]=8,$ then A represents the number $61280+71281+81282.$

Implementation

with a function problem. Implement your solutions in this function. Do not make any changes

outside of that function $($e$.$ g$.$ by adding helper functions$)$; such changes will be undone. Do

not output anything to the terminal.

randomly generates test cases. The seed of

the random number generator is set to ensure the same test cases whenever to program is executed.

Note that the purpose of the tests is for you to avoid major mistakes. Passing all given tests does

not imply that your algorithm is correct, especially that is has the expected runtime.

Submission

This is an individual assignment. Therefore, a submission is required from each student.

Deadline: On Canvas

$1$ The algorithm you are expected to implement, strictly speaking, runs in O$($b $$ n$)$ time, where b is the base for counting

The program already implemented in the file Lab$6.$java

For your submission, upload the file Lab$6.$javawith your implement to canvas.

You are given a file Lab$6.$java $($which you can download from canvas$).$ The file contains a class lab$6$