In our latest set of Sledgecasts I work through the problem of merging k sorted lists. I eventually converged on the optimal solution except I did not perform it in place. Merging linked lists can be done in place without any allocation which can make a big difference if you are allocating an entirely new list each time you merge.