Minimum external sort files

An external sort turns a stream of records into sorted runs before it merges them. Records arrive one at a time in a fixed order, and every open run file has to stay non-decreasing on the sort key, so a record can be appended to an open file only when its key is at least the last key that file already holds. When no open file can take a record, the sort has to open another one. Every record is written exactly once, and no record is held back or reordered. Given the keys in arrival order, return the fewest files the sort can finish with. Keys are integers, they may repeat, and they may be negative. An empty stream needs no files at all. Appending to any file that happens to fit is not the same as appending to the right one.