Mullsortimine

Jõudlus

Nii halvimal kui ka keskmisel juhul on mullimeetodi keerukus O(n²), kus n on sorditavate elementide hulk. On palju sortimisalgoritme, mille halvima või keskmise juhu jõudlus on oluliselt parem, nt O(n log n). Seega pole mullimeetod suure n väärtuse korral otstarbekas.
Mullimeetodi eelis paljude teiste sortimisalgoritmide (sh kiirsortimise) ees on suutlikkus kiiresti tuvastada olukord, kus loend on juba sorditud. Mullsortimise keerukus juba sorditud loendi korral (parim juhtum) on O(n). Selline omadus on ka näiteks vahelepanemisega sortimisel.
Mullimeetod on stabiilne ja töötab kohapeal ehk ei vaja lisamälu.

Küülikud ja kilpkonnad

Mullimeetodi jõudluse määrab suuresti elementide asetus. Suuri elemente loendi alguses vahetatakse tihti, seega liiguvad need kiiresti oma õigele kohale. Väikesed elemendid loendi lõpus liiguvad algusse aga väga aeglaselt. Selliseid elemente on hakatud kutsuma vastavalt küülikuteks ja kilpkonnadeks.

Sammhaaval näide

Antud on loend elementidega 8, 1, 5, 2 ja 4, mida sorditakse mullimeetodil väiksemast suuremani. Igal sammul on võrreldavad elemendid kirjutatud paksus kirjas.
Esimene läbimine:

( 8 1 5 2 4 )  ( 1 8 5 2 4 ) Algoritm võrdleb kahte esimest elementi ning vahetab nende järjestuse, kuna 8 > 1

( 1 8 5 2 4 )  ( 1 5 8 2 4 ) Vahetus, kuna 8 > 5 

( 1 5 8 2 4 )  ( 1 5 2 8 4 ) Vahetus, kuna 8 > 2 

( 1 5 2 8 4 )  ( 1 5 2 4 8 ) Vahetus, kuna 8 > 4 

Igal läbimisel "mullitab" võrreldud elementidest suurim õigesse kohta loendi sorditud järjestuses. See tähendab, et igal järgmisel läbimisel tuleb võrrelda ühe võrra vähem elemente.
Teine läbimine:

( 1 5 2 4 8 )  ( 1 5 2 4 8 ) Kuna elemendid on juba õiges järjestuses (1 < 5), siis vahetust ei toimu

( 1 5 2 4 8 )  ( 1 2 5 4 8 ) Vahetus, kuna 5 > 2 

( 1 2 5 4 8 )  ( 1 2 4 5 8 ) Vahetus, kuna 5 > 4 

Nüüdseks on loend sorditud, kuid algoritm pole seda veel tuvastanud ja jätkab.
Kolmas läbimine:

( 1 2 4 5 8 )  ( 1 2 4 5 8 )

( 1 2 4 5 8 )  ( 1 2 4 5 8 )

Algoritm lõpetab töö, kuna sellel läbimisel ei tehtud ühtegi vahetust ja see tähendab, et loend on sorditud.

Pseudokood

Algoritmi võib esitada kujul:
 procedure bubbleSort( A : list of sortable items )
   do
     swapped := false
     for each i in 0 to length(A) - 2 inclusive do:
       if A[i] > A[i+1] then
         swap( A[i], A[i+1] )
         swapped := true
       end if
     end for
   while swapped
 end procedure

Jõudluse parandus

Mullimeetodi jõudlust saab parandada, kui arvestada, et pärast igat läbimist jõuab võrreldud elementidest suurim oma lõplikule kohale loendi lõpuosas. Loendi lõppu jõudnud elemendid on sorditud ja neid enam läbima ei pea. Näiteks suurusega n loendi korral on n-is element on oma lõplikul positsioonil pärast esimest läbimist. Teisel läbimisel jääb sortida n - 1 elementi. Pärast teist läbimist on element n - 1 oma lõplikul positsioonil ja nii edasi.
 procedure bubbleSort( A : list of sortable items )
   n := length( A )
   do
     swapped := false
     for each i in 0 to n - 1  inclusive do:
       if A[ i ] > A[ i + 1 ] then
         swap( A[ i ], A[ i + 1 ] )
         swapped := true
       end if
     end for
     n := n - 1
   while swapped
 end procedure
Selle asemel, et teha  võrdlust, tehakse maksimaalselt  võrdlust. Täitmisaeg on ikka , kuid halvimal juhul (sisendandmed on kahanevas järjestuses) on mullimeetod selle täiendusega kaks korda kiirem.

C

Näidislahendus C-s:
void bubbleSort(int numbers[], int numbers_size) {
    int n, i;
    for (n = numbers_size - 1; n > 0; n--) {
        for (i = 1; i <= n; i++) {
            int left = numbers[i - 1];
            int right = numbers[i];
            if (left > right) {
                numbers[i - 1] = right;
                numbers[i] = left;
            }
        }
    }}int numbers[] = { 8, 1, 5, 2, 4 };bubbleSort(numbers, 5);

Praktiline kasutus

Kuigi mullsortimine on mõistmise ja teostamise seisukohalt üks lihtsamaid sortimisalgoritme, pole see ajalise keerukuse O(n²) tõttu tõhus, et kasutada seda mõnest elemendist suuremate loendite korral. Isegi teiste lihtsate O(n²) sortimisalgoritmide hulgas on üldjuhul tõhusamaid algoritme, näiteks vahelepanekuga sortimine.
Tänu oma lihtsusele kasutatakse mullsortimist tihti algajatele arvutiteaduse tudengitele algoritmi või sortimisalgoritmi kontseptsiooni tutvustamiseks. Samas on mõned arvutiteadlased, näiteks Owen Astrachan, vastu mullsortimise kasutamisele ja õpetamisele, kuna see leiab praktikas vähe kasutust.