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) time1. 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 6128^0 +7128^1 +8128^2.

Implement problem() method with no outside methods or helper functions. The code below problem() runs test cases on the implemented code within problem().

import java.io.*; import java.util.*; public class IntegerSort { /** * Problem: Sort multi-digit integers (with n total digits) in O(n) time. * (Technically, it is O(n * b) time. However, since our base b = 128 is constant, it is O(n).) */ private static void problem(byte[][] arr) { //IMPLEMENT } // --------------------------------------------------------------------- // Do not change any of the code below! private static final int LabNo = 6; private static final Random rng = new Random(654321); private static boolean testProblem(byte[][] testCase) { byte[][] numbersCopy = new byte[testCase.length][]; // Create copy. for (int i = 0; i < testCase.length; i++) { numbersCopy[i] = testCase[i].clone(); } // Sort problem(testCase); Arrays.sort(numbersCopy, new numberComparator()); // Compare if both equal if (testCase.length != numbersCopy.length) { return false; } for (int i = 0; i < testCase.length; i++) { if (testCase[i].length != numbersCopy[i].length) { return false; } for (int j = 0; j < testCase[i].length; j++) { if (testCase[i][j] != numbersCopy[i][j]) { return false; } } } return true; } // Very bad way of sorting. private static class numberComparator implements Comparator { @Override public int compare(byte[] n1, byte[] n2) { // Ensure equal length if (n1.length < n2.length) { byte[] tmp = new byte[n2.length]; for (int i = 0; i < n1.length; i++) { tmp[i] = n1[i]; } n1 = tmp; } if (n1.length > n2.length) { byte[] tmp = new byte[n1.length]; for (int i = 0; i < n2.length; i++) { tmp[i] = n2[i]; } n2 = tmp; } // Compare digit by digit. for (int i = n1.length - 1; i >=0; i--) { if (n1[i] < n2[i]) return -1; if (n1[i] > n2[i]) return 1; } return 0; } } public static void main(String args[]) { System.out.println("CS 302 -- Lab " + LabNo); testProblems(); } private static void testProblems() { int noOfLines = 10000; System.out.println("-- -- -- -- --"); System.out.println(noOfLines + " test cases."); boolean passedAll = true; for (int i = 1; i <= noOfLines; i++) { byte[][] testCase = createTestCase(i); boolean passed = false; boolean exce = false; try { passed = testProblem(testCase); } catch (Exception ex) { passed = false; exce = true; } if (!passed) { System.out.println("Test " + i + " failed!" + (exce ? " (Exception)" : "")); passedAll = false; break; } } if (passedAll) { System.out.println("All test passed."); } } private static byte[][] createTestCase(int testNo) { int maxSize = Math.min(100, testNo) + 5; int size = rng.nextInt(maxSize) + 5; byte[][] numbers = new byte[size][]; for (int i = 0; i < size; i++) { int digits = rng.nextInt(maxSize) + 1; numbers[i] = new byte[digits]; for (int j = 0; j < digits - 1; j++) { numbers[i][j] = (byte)rng.nextInt(128); } // Ensures that the most significant digit is not 0. numbers[i][digits - 1] = (byte)(rng.nextInt(127) + 1); } return numbers; } }