What sort to use?

Question

Java

Foreword:
I found an interesting task on the Internet by googling, I understood what it is on testing before an interview.

Question:
The task is clear to me, as I understand it, it rests on sorting, I solved the task itself. But here it is impossible to make it run in the specified 1-10 seconds. As I understand it, you need to do sorting, which has a speed of log2 (N). Could you tell me at what stage it is better to do (When the dictionary is just being filled in or immediately after it was filled up or when the necessary words were found) sorting and what kind of sorting to do (While I'm thinking about Shell sorting, but maybe there is better) ???

Answer 1

Who knows what you did there. In theory, it would be necessary to build a prefix tree based on a set of words, in each node of which there is a one-letter prefix (there is no need for a prefix at the root), the number of words starting with it and its parents, and links (no more than 26 - according to the number of letters of the alphabet) to children nodes.
When calling, you need to select a perfix branch and sort its child nodes. For such short arrays, insertion sort is relevant (yes, yes), but if you want to show off, choose something else .