2

We investigate the worst case complexity regarding the number of comparisons for a simple and stable merging algorithm. The complexity analysis shows that the algorithm performs log comparisons for two sequences of sizes and. So, according to the lower bound for merging log, the algorithm is asymptotically optimal regarding the number of comparisons. For proving the worst case complexity we divide the domain of all inputs into two disjoint cases. For either of these cases we will extract a special subcase and prove the asymptotic optimality for these two subcases. Using this knowledge for special cases we will prove the optimality for all remaining cases. By using this approach we give a transparent solution for the hardly tractable problem of delivering a clean complexity analysis for the algorithm. Key Words: stable merging, minimum storage, complexity of algorithms 1