Need help speeding up this jQuery process

Question

I've created the following process. Basically it loops through a gigantic unordered list with multiple level nested lists and creates a 2 level nested unordered list. It works well but is very slow in IE7. FireFox and Safari have no big problems with it. Not very good at jQuery I was wondering if I could speed up this by using better/faster/smarter functions. Due to the CMS I am using I can not change the output nor jQuery version I'm using which is 1.2.6.

Here's what I've got;

$('ul#mainnav li ul li').each(function() {
    // add level class
    $(this).addClass('depth-'+$(this).parents('ul').length);
    // make uls siblings in stead of children
    $($(this).children('ul')).insertAfter($(this));
});
// take all lis out of their uls
$('ul#mainnav li ul').each(function() {
    $(this).replaceWith($(this).children());                
});
// wrap chidlren lis with div
$('ul#mainnav li').each(function() {
    $(this).children('li:first').before('<ul class="megamenu" />');     
    $(this).children('.megamenu').append($(this).children('li'));
});
// apply plugin easyLisSplitter
$('.megamenu').easyListSplitter({ 
    colNumber: 5
});

Any ideas? If more info is needed let me know!

Cheers

EDIT:

Thanx for all the replies. Haven't tried everyting yet. Using var $this = $(this); sped up things by 20 milliseconds. Well I'll take those. All help is still welcome! Here's the before markup:

<ul id="mainnav">
<li><a href="#">A-1</a>
    <ul>
        <li><a href="#">A-1-1</a>
            <ul>
                <li><a href="#">A-1-1-1</a></li>
                <li><a href="#">A-1-1-2</a></li>
                <li><a href="#">A-1-1-3</a></li>
            </ul>
        </li>
        <li><a href="#">A-1-2</a></li>
        <li><a href="#">A-1-3</a>
            <ul>
                <li><a href="#">A-1-3-1</a></li>
                <li><a href="#">A-1-3-2</a></li>
                <li><a href="#">A-1-3-3</a></li>
            </ul>
        </li>
        <li><a href="#">A-1-4</a>
            <ul>
                <li><a href="#">A-1-4-1</a></li>
                <li><a href="#">A-1-4-2</a></li>
                <li><a href="#">A-1-4-3</a></li>
                <li><a href="#">A-1-4-4</a></li>
                <li><a href="#">A-1-4-5</a></li>
            </ul>
        </li>
        <li><a href="#">A-1-5</a>
            <ul>
                <li><a href="#">A-1-5-1</a></li>
                <li><a href="#">A-1-5-2</a></li>
                <li><a href="#">A-1-5-3</a></li>
                <li><a href="#">A-1-5-4</a></li>
                <li><a href="#">A-1-5-5</a></li>
            </ul>
        </li>
    </ul>
</li>
<li><a href="#">B-1</a>
    <ul>
        <li><a href="#">B-1-1</a>
            <ul>
                <li><a href="#">B-1-1-1</a></li>
                <li><a href="#">B-1-1-2</a></li>
                <li><a href="#">B-1-1-3</a></li>
            </ul>
        </li>
        <li><a href="#">B-1-2</a></li>
        <li><a href="#">B-1-3</a>
            <ul>
                <li><a href="#">B-1-3-1</a></li>
                <li><a href="#">B-1-3-2</a></li>
                <li><a href="#">B-1-3-3</a></li>
            </ul>
        </li>
        <li><a href="#">B-1-4</a>
            <ul>
                <li><a href="#">B-1-4-1</a></li>
                <li><a href="#">B-1-4-2</a></li>
                <li><a href="#">B-1-4-3</a></li>
                <li><a href="#">B-1-4-4</a></li>
                <li><a href="#">B-1-4-5</a></li>
            </ul>
        </li>
        <li><a href="#">B-1-5</a>
            <ul>
                <li><a href="#">B-1-5-1</a></li>
                <li><a href="#">B-1-5-2</a></li>
                <li><a href="#">B-1-5-3</a></li>
                <li><a href="#">B-1-5-4</a></li>
                <li><a href="#">B-1-5-5</a></li>
            </ul>
        </li>
    </ul>
</li>

And here's the after;

<ul id="mainnav">
<li><a href="#">A-1</a>
    <div class="listContainer1">
        <ul class="megamenu listCol1">
            <li class="depth-2"><a href="#">A-1-1</a></li>
            <li class="depth-3"><a href="#">A-1-1-1</a></li>
            <li class="depth-3"><a href="#">A-1-1-2</a></li>
            <li class="depth-3"><a href="#">A-1-1-3</a></li>
            <li class="depth-2"><a href="#">A-1-2</a></li>
        </ul>
        <ul class="listCol2 megamenu">
            <li class="depth-2"><a href="#">A-1-3</a></li>
            <li class="depth-3"><a href="#">A-1-3-1</a></li>
            <li class="depth-3"><a href="#">A-1-3-2</a></li>
            <li class="depth-3"><a href="#">A-1-3-3</a></li>
            <li class="depth-2"><a href="#">A-1-4</a></li>
        </ul>
        <ul class="listCol3 megamenu">
            <li class="depth-3"><a href="#">A-1-4-1</a></li>
            <li class="depth-3"><a href="#">A-1-4-2</a></li>
            <li class="depth-3"><a href="#">A-1-4-3</a></li>
            <li class="depth-3"><a href="#">A-1-4-4</a></li>
            <li class="depth-3"><a href="#">A-1-4-5</a></li>
        </ul>
        <ul class="listCol4 megamenu">
            <li class="depth-2"><a href="#">A-1-5</a></li>
            <li class="depth-3"><a href="#">A-1-5-1</a></li>
            <li class="depth-3"><a href="#">A-1-5-2</a></li>
            <li class="depth-3"><a href="#">A-1-5-3</a></li>
            <li class="depth-3"><a href="#">A-1-5-4</a></li>
        </ul>
        <ul class="listCol5 megamenu last">
            <li class="depth-3"><a href="#">A-1-5-5</a></li>
        </ul>
    </div>
</li>
<li><a href="#">B-1</a>
    <div class="listContainer2">
        <ul class="megamenu listCol1">
            <li class="depth-2"><a href="#">B-1-1</a></li>
            <li class="depth-3"><a href="#">B-1-1-1</a></li>
            <li class="depth-3"><a href="#">B-1-1-2</a></li>
            <li class="depth-3"><a href="#">B-1-1-3</a></li>
            <li class="depth-2"><a href="#">B-1-2</a></li>
        </ul>
        <ul class="listCol2 megamenu">
            <li class="depth-2"><a href="#">B-1-3</a></li>
            <li class="depth-3"><a href="#">B-1-3-1</a></li>
            <li class="depth-3"><a href="#">B-1-3-2</a></li>
            <li class="depth-3"><a href="#">B-1-3-3</a></li>
            <li class="depth-2"><a href="#">B-1-4</a></li>
        </ul>
        <ul class="listCol3 megamenu">
            <li class="depth-3"><a href="#">B-1-4-1</a></li>
            <li class="depth-3"><a href="#">B-1-4-2</a></li>
            <li class="depth-3"><a href="#">B-1-4-3</a></li>
            <li class="depth-3"><a href="#">B-1-4-4</a></li>
            <li class="depth-3"><a href="#">B-1-4-5</a></li>
        </ul>
        <ul class="listCol4 megamenu">
            <li class="depth-2"><a href="#">B-1-5</a></li>
            <li class="depth-3"><a href="#">B-1-5-1</a></li>
            <li class="depth-3"><a href="#">B-1-5-2</a></li>
            <li class="depth-3"><a href="#">B-1-5-3</a></li>
            <li class="depth-3"><a href="#">B-1-5-4</a></li>
        </ul>
        <ul class="listCol5 megamenu last">
            <li class="depth-3"><a href="#">B-1-5-5</a></li>
        </ul>
    </div>
</li>

Answer 1

Another thing that should help is to eliminate redundant jquery calls by storing the resultant object in a variable. For example, change this:

$('ul#mainnav li ul li').each(function() {
    // add level class
    $(this).addClass('depth-'+$(this).parents('ul').length);
    // make uls siblings in stead of children
    $($(this).children('ul')).insertAfter($(this));
});

to this:

$('ul#mainnav li ul li').each(function() {
    var $this = $(this);
    // add level class
    $this.addClass('depth-'+$this.parents('ul').length);
    // make uls siblings in stead of children
    $($this.children('ul')).insertAfter($this);
});

Note the convention of starting a var name with $ when it refers to a jquery object.

Also, I'm not sure, but I think there's a more direct way to append to a list of children which might simplify the last line of the above code. Maybe something like $this.children('ul').append?

As the other answers say, only alter the live dom once. Another way to do this is to clone the whole structure that you're working on, manipulate the clone, and then replace the original with the clone. However you do it, the key is to avoid the browser trying to render each change as it's made.