Suppose that two entries of an array A are equal to each other. After running the insertion-sort algorithm of Code Fragment 3.7, will they appear in the same relative order in the final sorted order or in reverse order? Explain your answer.

Data from in Fragment 3.7

Algorithmic description of the insertion-sort algorithm. temporary variables are needed, how the loops are structured, and what decisions need to be made. We illustrate an example run in Figure 3.5. We present C++ code for our insertion-sort algorithm in Code Fragment 3.8. We assume that the array to be sorted consists of elements of type char, but it is easy to generalize this to other data types. The array A in the algorithm is implemented as a char array. Recall that each array in C++ is represented as a pointer to its first element, so the parameter A is declared to be of type char*. We also pass the size of the array in an integer parameter n. The rest is a straightforward translation of the description given in Code Fragment 3.7 into C++ syntax.

void insertionSort(char* for (int i = 1; i = 0) && (A[i]> cur)) { A[j+ 1] = A[j]; j-; } A[i+1] = cur; // sort an array of n characters // insertion loop // current character to insert // start at previous character // while A[j] is out of order // move A[j] right // decrement j // this is the proper place for cur