please do Q3 and Q4

I will give a like

3. You are given an array of strings of lowercase letters, where different strings may have different numbers of characters: let the total number of characters across all strings (NOT the total number of strings in the array) be n. Describe (in words, not pseudocode) a method to sort the array in standard alphabetical order. Then explain what the worst-case runtime of your algorithm is, in terms of only n, the total number of characters across all strings, and why that runtime is correct. Example: sorting the array ["cba", "b", "abc", "cb", "a"] would output ["a", "abc", "b", "cb", "cba"] and n=10 for this example. Hint 1: If you plan on using Radix Sort, how do you handle the fact that you might at some point be sorting strings based on the ith character, when not all strings in the array have at least i characters? Hint 2: When analyzing the runtime, consider the case where your array consists of one string of length (n/2), and (n/2) strings of length 1 . 4. You can see from the decision tree below, that it is possible to sort any array of 3 numbers within 3 comparisons. Each internal node here represents one comparison (for example 1:2 is comparing the elements initially at index 1 and index 2 ). If we hit a leaf node, then we have narrowed the possibilities down to only one permutation of the original list, so we have our sorted order. Since all 6 possible permutations of the array appear in this decision tree of height 3 , we can sort any 3 element array in 3 comparisons. Prove that for any comparison-based sorting algorithm used on an array of n elements, if n>4, then for most permutations the array can't be sorted within n comparisons (that is, more than half of the permutations are not in the first n levels of the decision tree). Hint: What is the maximum number of leaves a decision tree of height h=n can have? How many permutations does an array of n elements have? Can you prove by induction that it's not possible for at least half of them to fit into the leaves of said tree