title: Can you formulate the Bubble sort as a monoid or semigroup?
body: <p>Given the following pseudocode for the bubble-sort</p>
  
  <pre><code>procedure bubbleSort( A : list of sortable items )
     repeat     
       swapped = false
       for i = 1 to length(A) - 1 inclusive do:
         /* if this pair is out of order */
         if A[i-1] &gt; A[i] then
           /* swap them and remember something changed */
           swap( A[i-1], A[i] )
           swapped = true
         end if
       end for
     until not swapped
  end procedure
  </code></pre>
  
  <p>Here is the code for Bubble Sort as Scala</p>
  
  <pre><code>def bubbleSort[T](arr: Array[T])(implicit o: Ordering[T]) {
    import o._
    val consecutiveIndices = (arr.indices, arr.indices drop 1).zipped
    var hasChanged = true
    do {
      hasChanged = false
      consecutiveIndices foreach { (i1, i2) =&gt;
        if (arr(i1) &gt; arr(i2)) {
          hasChanged = true
          val tmp = arr(i1)
          arr(i1) = arr(i2)
          arr(i2) = tmp
        }
      }
    } while(hasChanged)
  }
  </code></pre>
  
  <p>This is the Haskell implementation:</p>
  
  <pre><code>bsort :: Ord a =&gt; [a] -&gt; [a]
  bsort s = case _bsort s of
                 t | t == s    -&gt; t
                   | otherwise -&gt; bsort t
    where _bsort (x:x2:xs) | x &gt; x2    = x2:(_bsort (x:xs))
                           | otherwise = x:(_bsort (x2:xs))
          _bsort s = s
  </code></pre>
  
  <p>Is it possible to formulate this as a monoid or semigroup?</p>