Is pandas.DataFrame.groupby Guaranteed To Be Stable?
<p>I've noticed that there are several uses of <a href="http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.groupby.html"><code>pd.DataFrame.groupby</code></a> followed by an <code>apply</code> implicitly assuming that <code>groupby</code> is <a href="http://stackoverflow.com/questions/1517793/stability-in-sorting-algorithms"><em>stable</em></a> - that is, if <em>a</em> and <em>b</em> are instances of the same group, and pre-grouping, <em>a</em> appeared before <em>b</em>, then <em>a</em> will appear pre <em>b</em> following the grouping as well. </p>

<p>I think there are several answers clearly implicitly using this, but, to be concrete, here is <a href="http://stackoverflow.com/questions/15755057/using-cumsum-in-pandas-on-group">one using <code>groupby</code>+<code>cumsum</code></a>.</p>

<p>Is there anything actually promising this behavior? The documentation only states:</p>

<blockquote>
  <p>Group series using mapper (dict or key function, apply given function to group, return result as series) or by a series of columns.</p>
</blockquote>

<p>Also, pandas having indices, the functionality could be theoretically be achieved also without this guarantee (albeit in a more cumbersome way).</p>

<p>Although the docs don't state this internally, it uses stable sort when generating the groups. </p>

<p>See: </p>

<ul>
<li><a href="https://github.com/pydata/pandas/blob/master/pandas/core/groupby.py#L291" rel="nofollow">https://github.com/pydata/pandas/blob/master/pandas/core/groupby.py#L291</a> </li>
<li><a href="https://github.com/pydata/pandas/blob/master/pandas/core/groupby.py#L4356" rel="nofollow">https://github.com/pydata/pandas/blob/master/pandas/core/groupby.py#L4356</a></li>
</ul>

<p>As I mentioned in the comments, this is important if you consider <code>transform</code> which will return a Series with it's index aligned to the original df. If the sorting didn't preserve the order, then this would make alignment perform additional work as it would need to sort the Series prior to assigning. In fact, this is mentioned <a href="https://github.com/Blosc/bcolz/issues/76" rel="nofollow">in the comments</a>:</p>

<blockquote>
  <p><code>_algos.groupsort_indexer</code> implements <strong>counting sort</strong> and it is at least
      <code>O(ngroups)</code>, where</p>
  
  <p><code>ngroups = prod(shape)</code></p>
  
  <p><code>shape = map(len, keys)</code></p>
  
  <p>That is, linear in the number of combinations (cartesian product) of unique
      values of groupby keys. This can be huge when doing multi-key groupby.
      <code>np.argsort(kind='mergesort')</code> is <code>O(count x log(count))</code> where count is the
      length of the data-frame;
      Both algorithms are <strong>stable</strong> sort and that is necessary for correctness of
      groupby operations. </p>
  
  <p>e.g. consider:
          <code>df.groupby(key)[col].transform('first')</code></p>
</blockquote>

python pandas group-by language-lawyer