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

[pbiggar]

Insertion sort is as easy (maybe easier) to write than bubblesort, and has better performance across the board.

[jules → pbiggar]

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.

[Groxx → pbiggar]

I don't know about insertion sort - you need to do a nested loop through the already-sorted part of the array to find where it should go (which requires knowing how much is already sorted), and move multiple values around when you insert it (easy in a linked list, harder in an array (another nested loop!)).

[sadga → Groxx]

Selection sort is simpler than Insertion sort.