top of page
Quick Merge Lists

This is code for a solution to a Merge K Sorted Linked Lists problem. This is, as far as I know, a novel solution to the problem. The best solutions utilize a divide and conquer approach, merging two lists at a time in a way that the lists are on average the same length, thus minimizing the number of comparisons done. Typically this is done iteratively by merging lists within a loop. My solution here takes a different approach, instead using a recursive divide and conquer algorithm similar to Quick Sort, effectively choosing a middle pivot element and merging the lists to the left of the pivot, and right of and including the pivot. This has similar performance to the iterative approach, having a Big O time complexity of O(N*Log(k)) in both cases, with N being the total number of nodes and K being the total number of lists.

Quick Merge Header

QuickMergeHeader.png

Quick Merge Implementation

QuickMergeSource.png
bottom of page