title: Go selection sort slower than bubble sort?
body: <p>I was doing some coding to practice algorithms, and I found something weird, when I implement the simple sorters in Python, with a random input of 99 elements, selection sort is faster than bubble sort:</p>
  
  <p><a href="https://i.stack.imgur.com/QNQyb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/QNQyb.png" alt="Python benchmark results"></a></p>
  
  <p>This is my bubble and insert sort implementations in Python:</p>
  
  <pre class="lang-py prettyprint-override"><code>from typing import List, TypeVar
  
  T = TypeVar('T')
  
  
  def bubble_sort(elems: List[T]) -&gt; List[T]:
      """Sorts a list using the bubble sort algorithm"""
      if not elems:
          return elems
  
      for mx in range(len(elems), 0, -1):
          for idx in range(1, mx):
              if elems[idx - 1] &gt; elems[idx]:
                  elems[idx - 1], elems[idx] = elems[idx], elems[idx - 1]
  
      return elems
  
  
  def selection_sort(elems: List[T]) -&gt; List[T]:
      """Sorts a list using the selection sort algorithm"""
      if not elems:
          return elems
      n = len(elems)
      for i in range(0, n):
          smidx = i
          for j in range(i + 1, n):
              if elems[smidx] &gt; elems[j]:
                  smidx = j
          elems[i], elems[smidx] = elems[smidx], elems[i]
      return elems
  </code></pre>
  
  <p>And of course, the test (using PyTest and PyTest Benchmark):</p>
  
  <pre class="lang-py prettyprint-override"><code>import random
  from sorting import *
  
  entry = [48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26]
  
  expected = list(range(1, 100))
  
  def test_bubble_sort(benchmark):
      x = entry.copy()
      assert benchmark(bubble_sort, x) == expected
  
  def test_select_sort(benchmark):
      x = entry.copy()
      assert benchmark(selection_sort, x) == expected
  </code></pre>
  
  <p>Now, when I try and implement the same algorithms in Go, I get worse numbers for my select sort implementation:</p>
  
  <pre class="lang-golang prettyprint-override"><code>package algo
  
  func BubbleSort(elems []int) []int {
      if elems == nil {
          return nil
      }
      for mx := len(elems) - 1; mx &gt;= 0; mx-- {
          for idx := 1; idx &lt;= mx; idx++ {
              if elems[idx-1] &gt; elems[idx] {
                  elems[idx-1], elems[idx] = elems[idx], elems[idx-1]
              }
          }
      }
      return elems
  }
  
  func Selection(elems []int) []int {
      if elems == nil {
          return nil
      }
      n := len(elems) - 1
      for i := 0; i &lt;= n; i++ {
          maxIdx := i
          for j := i + 1; j &lt;= n; j++ {
              if elems[j] &lt; elems[maxIdx] {
                  maxIdx = j
              }
          }
          elems[i], elems[maxIdx] = elems[maxIdx], elems[i]
      }
      return elems
  }
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/C0KpV.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/C0KpV.png" alt="Go benchmark results"></a></p>
  
  <p>Here is the test:</p>
  
  <pre class="lang-golang prettyprint-override"><code>func BenchmarkBubbleSort(b *testing.B) {
      for n := 0; n &lt; b.N; n++ {
          var longSeq = []int{48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26}
          BubbleSort(longSeq)
      }
  }
  
  func BenchmarkSelectionSort(b *testing.B) {
      for n := 0; n &lt; b.N; n++ {
          var longSeq = []int{48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26}
          Selection(longSeq)
      }
  }
  </code></pre>
  
  <p>Yes, I know select sort can be worse than bubble sort for the best case scenario (I don't think it is this the case based in a shuffled input), but why, if that is the case, why in Python it behaves like expected? (faster than bubble sort).</p>
  
  <p>I tried already changing the for loops to range in Go but the timing is similar. Maybe somebody has an idea what is happening here?</p>
  
  <p>Thanks a lot</p>