$3$ Sorted Array with Sidekick

Storing items in a sorted array has the advantage that binary search can find an item in $(logn)$ time. However, insertion into a sorted array is cumbersome and takes $(n)$ time.

A Sorted Array with Sidekick $($SAwS$)$ combines a sorted array with a smaller unsorted array, the sidekick. New items inserted in a SAwS are added to the sidekick array, which takes $O(1)$ actual time since the sidekick is not sorted. When the number of items in the sidekick grows beyond $\sqrt[\phantom{2}]{n},$ the sidekick is sorted and merged into the sorted array. After this merger, the new sidekick is empty. To search in a SAwS simply do a binary search in the main array and a linear search in the sidekick.

Throughout this problem, let $n$ be the number of items currently stored in the SAwS. This means $n$ changes when items are added to or removed from the SAwS. You should analyze the running times in terms of $n.$

Just assume that the arrays have enough space allocated. It is possible to combine this data structure with dynamic tables, but let's keep it simple.

Again, for simplicity, just assume that in our use case we will never insert duplicate keys into this data structure. $($It is possible to handle duplicates, but it gets rather complicated when we delete a key that has duplicates still in the SAwS.$)$

You know nothing about the type, distribution or range of the keys. So you cannot use counting sort, bucket sort, radix sort or any linear$-$time sorting algorithm.

You may assume without further comment that in the worst case sorting $m$ items takes $(mlogm)$ time, binary search in a sorted array of $m$ items takes $(logm)$ time, finding the median of an unsorted array of $m$ items takes $(m)$ time and merging two sorted arrays of $m$ and $l$ items takes $(m+l)$ time.

Do not write pseudo$-$code. If you want to sort an array $A,$ just say "Sort the array $A."$

Questions:

Briefly describe how the sidekick array can be merged into the sorted array in $(n)$ actual time.

Using the accounting method, show that the insert and search operations in a SAwS can be accomplished in $O(\sqrt[\phantom{2}]{n})$ amortized time. $($Ignore the delete operation for now.$)$

Note: State an invariant for your accounting scheme and argue that the invariant is maintained after each insert and search operation, including operations that merge the sidekick into the sorted array.

Describe how to implement the delete operation in a SAwS so that search, insert and delete each takes $O(\sqrt[\phantom{2}]{n})$ amortized time.

The delete operation is given a key $x$ and must find then remove $x$ from the SAwS data structure. For sorted arrays, it is convenient to simply mark the location of $x$ as "removed". $($Assume the programming language supports this.$)$ For unsorted arrays, you can either mark $x$ as removed or move the last item to the vacated location. However, $n$ is still the number of items in the SAwS and does not include the locations marked "removed".

Note that a delete makes either the main array or the sidekick array smaller by $1$ and that repeated deletions reduce the values of $n$ and $\sqrt[\phantom{2}]{n}$ significantly. In particular, the size of the sidekick array might exceed $\sqrt[\phantom{2}]{n}$ not because we added items to the sidekick, but because the value of $n$ is reduced.

Note: You should revise the invariant for your accounting scheme and argue that the invariant is maintained after each insert, delete and search operation, including operations that merge the sidekick into the sorted array.