I tried my best to use concepts I know so far to make this as fast as possible while keeping the memory requirements and the layout reasonable
one improvement could be to only sort and use binary search for huge array2 arrays and rely on the cache speed for smaller ones with linerar search

This solution adds extra spaces for new words which are allready uppercase, as far as I understood this was not the task. Also there is no allocation for on empty string which still needs termination (as far as I know strlen does not count the null termination).
I think this produces a wrong output for "abc D" which is "abc D" and I think if called with "" is undefined behaivior or system dependend

lets put them in an array an use binary search xd