Another exercise:

1000 name tags were printed and sorted by first name into a stack. A person wishes to instead sort the tags by last name.

How can you fix this?

Solution 1:

For each tag, insert that tag into the proper location in a new last-name sorted stack.

Solution approach 1 will be very hard; finding the correct insertion location in the new sorted stack will take time once that stack has about 100 or more items.

Solution 2: For each tag, place the tag into one of 26 sub-stacks, one for last names starting with A, one for B, etc. Then, for each sub-stack's tags (like the A stack), insert that tag into the proper location of a last-name sorted stack for that letter. Finally combine the stacks in order (A's stack on top, then B's stack, etc.)

Solution approach 2 is faster, because initially dividing into the 26 stacks is easy, and then each stack is relatively small so easier to do the insertions.

write a program using MatLab to solve this problem using the Solution 2 approach!