Sorted Array Insertion

a) Implement the fastest possible algorithm to insert a new entry into a sorted (in ascending order) array of strings. Duplicates are NOT allowed - throw an IllegalArgumentException if a duplicate is attempted to be inserted. After insertion, the array should still be in sorted order.

You will get at most half the credit if your algorithm is not the fastest possible. (Fastest here refers to the real clock time, not big O, for large values of n).

// Inserts a string into a sorted array A, containing n entries, where n is

// strictly less than the length of the array. (There are more spaces in the

// array than entries.) Throws an IllegalArgumentException if string already exists

// (case insensitive match).

// After the insertion, the array is still sorted.

public static void sortedInsert(String[] A, int n, String item) {

b) What is the worst case big O running time for your implementation? Identify the basic operations and show how they add up to the running time. (For any of the search algorithms done in class, you may assume its known running time without derivaton.)

You will not get any credit without an adequate derivation, even if your answer is correct.