Question 1:

You are required to undertake a detailed analysis of the AVL tree sorting algorithm for avl_sort.

To do this, consider to

1) provide a description of the algorithm in pseudocode;

2) conduct time complexity analysis of the algorithm (and also mention best case and worst case scenarios);

3) Hand test your algorithm using your allocated 10-element long list of alphabetic characters as an illustrative/working example (see the Data Set below),

o count the number of comparisons;
o estimate the algorithm's storage requirement;
o re-arrange your data set so as to achieve the best-case sorting of the algorithm; and
o re-arrange your data set so as to achieve the worst-case sorting of the algorithm.

Question 2:

You are required to undertake a detailed analysis of the following sorting algorithm applied to sorting the multiway tree (of order 4 type) data structure:

- m_tree_sort
- b_tree_sort

Similar to the case of Question 1, analyse the algorithms by
1) providing a description of the algorithm in pseudocode;
2) conducting time complexity analysis of the algorithm (and also mention best and worst case analysis/scenarios if applicable);
3) hand testing your algorithm using your allocated 10-element long list of alphabetic characters as an illustrative/working example (see the Data Set below),
o count the number of comparisons;
o estimate the algorithm's storage requirement;
o re-arrange your data set so as to achieve the best-case sorting of the algorithm;
o re-arrange your data set so as to achieve the worst-case sorting of the algorithm.