We talked about Sorted Arrays, but we didn't talk about how to create them, which is called "Sorting". You don't need to master sorting algorithms for an interview. To be safe, you might want to at least understand HeapSort and MergeSort.

Sorting arbitrary items in general requires comparing elements with each other. You can prove this takes at least $O(n \log n)$ time. This applies to all comparison sort algorithms: HeapSort, MergeSort, and QuickSort.

Counting Sort and Radix Sort are not comparsion sort algorithms - they only work on integers and other discretely-spaced elements. That's why they're allowed to run faster, in $O(n+|\text{range}|)$ and $O(n \cdot |\text{digits}|)$ time.

Python's built-in sorting functions .sort() and sorted() run "TimSort" in the background (a MergeSort variant).