title: What is this odd sorting algorithm?
body: <p>Some <a href="https://stackoverflow.com/a/69435932/16759116">answer</a> originally had this sorting algorithm:</p>
  <pre class="lang-none prettyprint-override"><code>for i from 0 to n-1:
      for j from 0 to n-1:
          if A[j] &gt; A[i]:
              swap A[i] and A[j]
  </code></pre>
  <p>Note that both <code>i</code> and <code>j</code> go the full range and thus <code>j</code> can be both larger and smaller than <code>i</code>, so it can make pairs both correct and wrong order (and it actually <em>does</em> do both!). I thought that's a mistake (and the author later called it that) and that this would jumble the array, but it does appear to sort correctly. It's not obvious why, though. But the <em>code</em> simplicity (going full ranges, and no <code>+1</code> as in bubble sort) makes it interesting.</p>
  <p><strong>Is it correct? If so, why does it work? And does it have a name?</strong></p>
  <p>Python implementation with testing:</p>
  <pre><code>from random import shuffle
  
  for _ in range(3):
      n = 20
      A = list(range(n))
      shuffle(A)
      print('before:', A)
  
      for i in range(n):
          for j in range(n):
              if A[j] &gt; A[i]:
                  A[i], A[j] = A[j], A[i]
  
      print('after: ', A, '\n')
  </code></pre>
  <p>Sample output (<a href="https://tio.run/##bU5BCsIwELznFXtLAjmIvUihQt@hRSomdku7CWk8@PqYpBUV3Mvsziwz455hsFQdnI/ReDuD7@mWAGdnfYBleBgzacaM9XABpKzftahkzSANQQP7XVnbtE64BLF@kJSF3hxEu57OIwXBrzoZ6porSHwRcgB@AmgLeEvjfykPGmhPYwfHBNj9aqVYYtX60hRQhWLffXoTtK8h91HAz8RljC8" rel="noreferrer" title="Python 3.8 (pre-release) – Try It Online">Try it online!</a>):</p>
  <pre><code>before: [9, 14, 8, 12, 16, 19, 2, 1, 10, 11, 18, 4, 15, 3, 6, 17, 7, 0, 5, 13]
  after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 
  
  before: [5, 1, 18, 10, 19, 14, 17, 7, 12, 16, 2, 0, 6, 8, 9, 11, 4, 3, 15, 13]
  after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 
  
  before: [11, 15, 7, 14, 0, 2, 9, 4, 13, 17, 8, 10, 1, 12, 6, 16, 18, 3, 5, 19]
  after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 
  </code></pre>
  <p>Edit: Someone pointed out a very nice brand new <a href="https://arxiv.org/abs/2110.01111" rel="noreferrer">paper</a> about this algorithm. Just to clarify: We're unrelated, it's a coincidence. As far as I can tell it was <em>submitted</em> to arXiv <a href="https://i.stack.imgur.com/0rF9E.png" rel="noreferrer"><em>before</em></a> that answer that sparked my question and <a href="https://web.archive.org/web/20211006015855/https://arxiv.org/list/cs.DS/recent" rel="noreferrer"><em>published</em></a> by arXiv <a href="https://i.stack.imgur.com/IC6lF.png" rel="noreferrer"><em>after</em></a> my question.</p>