Algoritmen til boblesortering kræver et par indlejrede sløjfer. Den ydre sløjfe skal gentage en gang for hvert element i datasættet (af størrelse n), mens den indre sløjfe gentager n gange første gang det indtastes, n-1 gange det andet osv. Overvej formålet med hver løkke. Som forklaret ovenfor er boblesortering struktureret således, at det næste største element i dataene flyttes til det rette sted for hver passage gennem listen. Derfor skal den ydre sløjfe udføres n gange for at få alle n-elementerne til deres rigtige steder.
Den indre sløjfe udføres på hver iteration af den ydre sløjfe. Formålet er at sætte det næststørste element på plads. Den indre sløjfe sammenligner og bytter derfor tilstødende elementer. For at bestemme kompleksiteten af denne sløjfe beregner vi antallet af sammenligninger, der skal foretages. På den første iteration af den ydre sløjfe, mens der forsøges at placere det største element, skal der være n – 1 sammenligninger: den første sammenligning foretages mellem det første og det andet element, det andet foretages mellem det andet og tredje element, og så videre, indtil n-1. sammenligningen foretages mellem n-1 og det n-element. På den anden iteration af den ydre sløjfe er det ikke nødvendigt at sammenligne det med det sidste element på listen, fordi det blev placeret på det rigtige sted ved det forrige pas. Derfor kræver den anden iteration kun n-2-sammenligninger. Dette mønster fortsætter indtil den næstsidste iteration af den ydre sløjfe, når kun de første to elementer på listen ikke er sorteret; klart i dette tilfælde er kun en sammenligning nødvendig. Det samlede antal sammenligninger er derfor (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 eller O (n2).
Det bedste tilfælde for boblesortering opstår, når listen allerede er sorteret eller næsten sorteret. I det tilfælde, hvor listen allerede er sorteret, afsluttes boblesortering efter den første iteration, da der ikke blev foretaget swaps. Hver gang der foretages et pass gennem listen, og der ikke blev foretaget swaps, er det sikkert, at listen er sorteret. Boblesortering er også effektiv, når et tilfældigt element skal sorteres i en sorteret liste, forudsat at nyt element placeres i begyndelsen og ikke i slutningen. Når den placeres i begyndelsen, bobler den simpelthen op til det rigtige sted, og den anden iteration gennem listen genererer 0 swaps og slutter sorteringen. Husk, at hvis det tilfældige element placeres i slutningen, mister boblesortering sin effektivitet, fordi hvert element, der er større end det, skal boble helt op til toppen.
Det absolut værste tilfælde for boblesortering er, når det mindste element på listen er i den store ende. Fordi kun det største usorterede element i hver iteration placeres på sin rette placering, når det mindste element er i slutningen, skal det byttes hver gang gennem listen, og det kommer ikke til fronten af listen, indtil alle n gentagelser er sket. I værste fald tager det n iterationer af n / 2 swaps, så ordren igen er n2.
Bedste sag: nGennemsnitlig sag: n2Værste sag: n2