EHN/FIX: Add na_last parameter to DataFrame.sort. Fixes GH3917
closes  #3917

This is an attempt to fix the Nested Sort with NaN bug (https://github.com/pydata/pandas/issues/3917).

I've added tests to `test_frame.py` and `test_hashtable.py` to demonstrate the problem.

`hashtable.Factorizer.factorize` has been modified to map `nan` to `na_sentinel`. Before it was mapping `nan` to a label which was already being used. This, I believe is the origin of the bug. 

My first idea was to mimick/reuse code from `Series.order`, since this method already handles `nan`s nicely, and allows the user to choose if nans should be placed at the beginning or the end of the sort via the `na_last` parameter. Although I found a solution using code from `Series.order`, I eventually abandoned this when I realized this patches the problem at too high a level and that it could be handled more generally with a modification of `factorize`. I retained the idea that `df.sort` should have a `na_last` parameter, however.

To that end, `groupby._lexsort_indexer` has been modified to handle all possible combinations of `na_last` and `orders` settings. There are four tests (assertions) in `test_frame.py` to exercise the possibilities, one of which demonstrates that `df.sort(['A','B'])` now behaves correctly for the DataFrame shown in GH3917.

interesting..this may go pretty far towards solving #5190
 I'd like time to review this - please don't merge for now.
 agreed..
 First, you need to put the new argument in last position _everywhere_ so
you don't break anything (and don't accidentally have users entering
something wrong - esp because usually no difference between 1 and True)

On external API - how about calling it `handle_na`, and then you can pass
either "rm" (remove them), "fill" (pass fill value), "last" (end up as
last), could also do "first" (end up as first) etc. this reminds me that I
need to add na-handling on apply and groupby as well. internal methods can
handle however they want.
 Okay, I'll put the new argument at the end. 

I'm a little hesitant about adding an `rm` option. Should a sort really be able to remove items? 

Instead of `handle_na='fill'`, how would you feel about a `key=func` parameter? Then instead of replacing NaNs with `fill_value`, we could use `func` to provide proxy values for NaNs: `key=lambda x: fill_value if np.isnan(x) else x`. 

The change to the code may be minimal: something like

```
k = func(self[x].values)
```
 @jtratner 

I don't think we need to mess with the na_last (as far as having complicated behavior)
why is the current not adequate ? 
 It seems awkward to me (na_position=last seems better or na_order=last). And if we're starting from the premise that we want to unify the API, would this apply flexibly to all the other sort methods? what about Series and Index  sorting? And to confirm, na_last=False makes them first? Removes them? And I'm assuming it's also supposed to maintain relative position? 
 Index doesn't have sort - so just Series and Panel. (groupby?) Assuming it applies to all. 
 this is just about sort ordering; you can't do a remove here; there are only 2 ways to do it, na_first or na_last (that said, you could do ti with a 'how' argument). Not sure we need to break the API here though
 Okay. na_last doesn't sound intuitive to me, but it seems like I'm in the
minority.
On Oct 15, 2013 4:47 PM, "jreback" notifications@github.com wrote:

> this is just about sort ordering; you can't do a remove here; there are
> only 2 ways to do it, na_first or na_last (that said, you could do ti with
> a 'how' argument). Not sure we need to break the API here though
> 
> —
> Reply to this email directly or view it on GitHubhttps://github.com/pydata/pandas/pull/5231#issuecomment-26370801
> .
 I like na_position better than na_last since I find `na_last=False` a bit confusing. But whatever you decide is fine with me. I'm going to hold off on adding a `key=func` parameter to a different pull request :) 
 And you can just check first letter if you want (so accept last, l, first,
f etc)
On Oct 15, 2013 5:03 PM, "unutbu" notifications@github.com wrote:

> I like na_position better than na_last since I find na_last=False a bit
> confusing. I'm going to hold off on adding a key=func parameter to a
> different pull request :)
> 
> —
> Reply to this email directly or view it on GitHubhttps://github.com/pydata/pandas/pull/5231#issuecomment-26371995
> .
 While I'm at it, would it be okay to change `orders` to `ascending` in groupby `_lexsort_indexer`? 
Or maybe I shouldn't break the API...
 Also, I neglected to say earlier - thanks for submitting this PR!
 Not totally clear on what you mean. That said, we can't change existing
behavior without a warning (but can add keyword arguments with defaults to
change behavior)
 Not at all, my pleasure.

It seems to me the keyword `ascending` as used in `DataFrame.sort` has the same meaning as `orders` as used in groupby's `_lexsort_indexer`. If that is true, it would be nice if only one name were used for the concept.
 If you change the parameter, nice to change name of PR too :) 
 @unutbu can you add a release notes/v0.13.0 entry (1-liner or small example in 0.13 if you want)

under API changes
 I've found a bug in my code. With `df` defined as in GH3917,  `df.sort(['A'], na_position='first')` does not place `NaN` at the beginning of the result.
 Glad you caught that! Still have some time to get this in for 0.13.
 Warning: My PR only affects how DataFrame.sort works when sorting columns with the `by` parameter. It doesn't currently address sorting by label. If `NaN` is a label, `na_position` does not affect the way it gets sorted...
 As I shift code away from argsort and onto `_lexsort_indexer`, the `kind` parameter is being used less and less. With my changes, `kind` is only used when sorting by label.
 okay, then you need to make the parameter None for now and then raise (NotImplementedError) if it is specified without a 'by' arg I guess.  But that said - better if you supported that.
 I like `na_position`...so in 0.14, then we will deprecate `na_last` for `Series.order` and change to na_position, yes? (aside from other fixups to Series.sort/order)

maybe want to add that warning now?
 @jreback I've added code to `core/series.py` to warn users that `na_last` is deprecated, and allow them to use the `na_position` parameter instead. 

@jtratner I've tried to extend `np.argsort` by adding `ascending` and `na_postion` parameters. The extended function, `_nargsort` is in `core/groupby`. I used `_nargsort` in `core/frame.py` to allow DataFrame to sort a single column or label while respecting `na_position`.
 Hm. Travis-CI does not like the changes I've made. I'm setting up new virtualenvs to debug this...
 I think there's some issue with mergesort not being fully implemented in numpy 1.6 - maybe you changed a default without realizing it?
 This error here - https://travis-ci.org/unutbu/pandas/jobs/12751402 - "`TypeError: unorderable types: str() > float()`", is likely occurring because you didn't mask out the nan values before the sort.
 (and by you here I mean "pandas with this PR")
 You're only going to see the 'unorderable types' error in Python 3. I suggest trying to fix that error _first_ - it could resolve the other one in the process.

You also might add a (temporary) assertion in your code to check that all the nan values have actually been filtered out where you think. That would make it easier to find the bug.
