Here is C++ code for a function that sorts strings

string stringSort(string s)

{

if (s.length() =>

return s;

string temp = stringSort(s.substr(1));

if (s[0] =>

{

return s[0] + temp;

}

return temp[0] + stringSort(s[0] + temp.substr(1));

}

Notes: s.substr(1) returns the substring of s that excludes the first character e.g. if s is "abc" then s.substr(1) is "bc". The plus operator means string concatenation. For example 'a' + "bc" gives the string "abc".

a) Explain in your own words why the stringSort function will return a string with the characters of s sorted in ascending order, for any string s.

b) Write a program that calls stringSort with strings of various lengths where the characters of each string are in descending order. Include a counter in your function right above the second if statement, to count the number of item comparisons for each input. Answer the questions below.

# of item comparisons for strings of length 1: __________________

# of item comparisons for strings of length 2: _________________

# of item comparisons for strings of length 3: _________________

# of item comparisons for strings of length 4: _________________

# of item comparisons for strings of length 5: _________________

# of item comparisons for strings of length 6: _________________

c) Find a polynomial f(n), of third degree that fits your results from part b. In other words f(1) should equal the first number, f(2) should equal the second number and so on. Explain how you came up with your polynomial. \

(In a more rigorous version of this question we would start by trying to fit the points to a polynomial of degree 1, then degree 2 etc. until finding the lowest degree polynomial that fits all six points. The outcome would be a polynomial of degree 3.)

d) Based on your result from Part c, how does the efficiency of stringSort compare with other sorting algoritms like bubblesort, mergesort etc. ?

In addtion to your answers to each part, upload the program you used for Part b.