@article {IOPORT.05041583,
    author       = {Keeffe, M.O. and Pajoohesh, H. and Schellekens, M.},
    title        = {The relationship between balance and the speed of algorithms.},
    year         = {2005},
    journal      = {Hadronic Journal},
    volume       = {28},
    number       = {5},
    issn         = {0162-5519},
    pages        = {531-558},
    publisher    = {Hadronic Press, Palm Harbor, FL},
    abstract     = {Summary: It is argued by {\it A. Aho}, {\it J. Hopcroft} and {\it J. Ullman} [Data structures and algorithms (1983; Zbl 0487.68005)] that Divide \& Conquer techniques which make a ``balanced" division lead to faster algorithms. We investigate the use of the imbalance lattice of (*) {\it D. S. Parker} and {\it P. Ram} [SIAM J. Comput. 28, 1875--1905 (1999; Zbl 0967.94005)] in the context of path-length sequences for decision trees of sorting algorithms. This forms a novel exploration of this lattice which prior to this has been restricted to the study of balance of trees, independently from running time. In this way we obtain a link between the balance of the decision tree of an algorithm and the speed of the algorithm. We use the imbalance lattice of (*) in the following to put this intuition on a formal basis. We use the imbalance lattice to show that mergesort has a better running time than insertion sort due to the fact that its decision tree is more balanced than that of insertion sort. We extend the imbalance lattice with an algebraic operation. This operation corresponds to the extension of a binary tree with new binary trees at the leafs, which reflects the effect of recursive calls of an algorithm on the decision tree. Finally, we also introduce a new representation for binary trees which enables us to represent the binary tree for mergesort in an inductive way.},
    identifier   = {05041583},
}