https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66962
--- Comment #12 from Markus Trippelsdorf <trippels at gcc dot gnu.org> --- This paper claims O(e log d) for size e and alternation depth d: http://www.win.tue.nl/~jfg/articles/CSR-04-13.pdf But I'm not sure if it is applicable.
