title: Is it possible to compute the sign of a permutation in linear time?
body: <p>I was just wondering if there's a way to compute the sign of a permutation within linear (or at least better than n^2?) time</p>
  <p>For example, let's say I have an array of n numbers and I permute two elements within this array which would flip the sign of the permutation. I have a function that can compute this in n^2  time, however, it seems there might be a more efficient algorithm.</p>
  <p>I've attached a minimal reproducible example of computing in quadratic time,</p>
  <pre><code>import numpy as np
  
  vals = np.arange(1,6,1)
  pvals = np.arange(1,6,1)
  pvals[0], pvals[1] = pvals[1], pvals[0] #swap
  
  def quadratic(vals):
    sgn_matrix = np.sign(np.expand_dims(vals, -1) - np.expand_dims(vals, -2))
    return np.prod(np.tril(np.ones_like(sgn_matrix)) + np.triu(sgn_matrix, 1))
  
  def sub_quadratic(vals):
    #algorithm quicker than quadratic time?
  
  sgn = quadratic(vals)
  print(sgn)   #prints +1 
  
  psgn = quadratic(pvals)
  print(psgn)  #prints -1 (because one permutation)
  </code></pre>
  <p>I have had a look around SO (<a href="https://math.stackexchange.com/questions/65923/how-does-one-compute-the-sign-of-a-permutation">here for example</a>) and people keep talking about cyclic permutations which apparently can compute in linear time but it's something I'm unaware of completely and can't find much of myself.</p>
  <p><strong>TL;DR</strong> Does anyone know of a method for computing the sign of a permutation in sub-quadratic time ?</p>