On: What’s really so bad about bubble sort?

[jules]

Nah, bubble sort is easier:

    for(i=0 to n):
      for(j=0 to n-1):
        if(a[j] > a[j+1]) swap(a[j],a[j+1])

-or-

    for(i=0 to n*n):
      j = i%(n-1)
      if(a[j] > a[j+1]) swap(a[j],a[j+1])
      

;-)

[pbiggar → jules]

Here's the actual sorts used in the paper:

Insertion: https://github.com/pbiggar/sorting-branches-caching/blob/mas...

Bubble: https://github.com/pbiggar/sorting-branches-caching/blob/mas...

Insertion sort is significantly faster (esp in branch prediction, they have similar cache locality, insertion sort has few comparisons and fewer moves and fewer overall instructions), is almost the same to implement, and is actually the fastest possible way to sort arrays of size 4 (and probably true up to about 30). So it's actually useful to know insertion sort, whereas bubblesort is actually useless.