请教之前遇到的一个面试题

Question

你好，之前去面试，有遇到一个算法题，问题是这样的：有两个list，A和B，
分别存储了不同的姓名，并且按照姓的首字母进行排序。现在要把A和B合并
成为一个list，并且也要求要按照姓的首字母进行排序，当时准备不充分，
没有答上来，想请教下，这个编码题该怎么做， 或者给个思路也行

Answer 1

最简单的方法就是两个list直接拼接，然后排序，这个时间复杂度肯定不是最优的。
最优的办法就是，两个指针下标给两个list，分别开始遍历，比较，哪个小，就加入到新list，并且下标加1。这样的时间复杂度是O(m+n)。