Repository: maxfischer2781/asyncstdlib

Issue:
Add sorted built-in
The `sorted` built-in seems like it would come useful:

```python
sorted_items = await sorted(my_aiter, key=my_key)
```

If it's omitted intentionally, feel free to reject this issue.

Discussion:
codecov[bot]: # [Codecov](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21?src=pr&el=h1) Report
> Merging [#21](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21?src=pr&el=desc) into [master](https://codecov.io/gh/maxfischer2781/asyncstdlib/commit/eef623202ee91410e33ec6bf7fe194f90cfe96e0?el=desc) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21/graphs/tree.svg?width=650&height=150&src=pr&token=frT6svSwUb)](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21?src=pr&el=tree)

```diff
@@           Coverage Diff           @@
##           master      #21   +/-   ##
=======================================
  Coverage   99.50%   99.51%           
=======================================
  Files           9        9           
  Lines         805      818   +13     
  Branches      131      135    +4     
=======================================
+ Hits          801      814   +13     
  Misses          4        4           
```


| [Impacted Files](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [asyncstdlib/\_\_init\_\_.py](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21/diff?src=pr&el=tree#diff-YXN5bmNzdGRsaWIvX19pbml0X18ucHk=) | `100.00% <ø> (ø)` | |
| [asyncstdlib/builtins.py](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21/diff?src=pr&el=tree#diff-YXN5bmNzdGRsaWIvYnVpbHRpbnMucHk=) | `98.67% <100.00%> (+0.12%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21?src=pr&el=footer). Last update [eef6232...31fa57d](https://codecov.io/gh/maxfischer2781/asyncstdlib/pull/21?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/asyncstdlib/__init__.py b/asyncstdlib/__init__.py
index 8478713..d833165 100644
--- a/asyncstdlib/__init__.py
+++ b/asyncstdlib/__init__.py
@@ -15,6 +15,7 @@ from .builtins import (
     dict,
     set,
     tuple,
+    sorted,
 )
 from .functools import reduce, lru_cache, cache, cached_property
 from .contextlib import closing, contextmanager, nullcontext, ExitStack
@@ -51,6 +52,7 @@ __all__ = [
     "dict",
     "set",
     "tuple",
+    "sorted",
     # functools
     "reduce",
     "lru_cache",
diff --git a/asyncstdlib/builtins.py b/asyncstdlib/builtins.py
index b3ad314..4091b8c 100644
--- a/asyncstdlib/builtins.py
+++ b/asyncstdlib/builtins.py
@@ -14,6 +14,7 @@ from typing import (
     Any,
     overload,
 )
+import builtins as _sync_builtins
 
 from typing_extensions import Protocol
 
@@ -410,3 +411,44 @@ async def set(iterable: Union[Iterable[T], AsyncIterable[T]] = ()) -> Set[T]:
     This is equivalent to ``{element async for element in iterable}``.
     """
     return {element async for element in aiter(iterable)}
+
+
+async def _identity(x: T) -> T:
+    """Asynchronous identity function, returns its argument unchanged"""
+    return x
+
+
+async def sorted(
+    iterable: AnyIterable[T],
+    *,
+    key: Optional[Callable[[T], Any]] = None,
+    reverse: bool = False,
+) -> List[T]:
+    """
+    Sort items from an (async) iterable into a new list
+
+    The optional ``key`` argument specifies a one-argument (async) callable, which
+    provides a substitute for determining the sort order of each item.
+    The special value and default :py:data:`None` represents the identity functions,
+    i.e. compares items directly.
+
+    The default sort order is ascending, that is items with ``a < b``
+    imply ``result.index(a) < result.index(b)``. Use ``reverse=True``
+    for descending sort order.
+
+    .. note::
+
+        The actual sorting is synchronous,
+        so a very large ``iterable`` or very slow comparison
+        may block the event loop notably.
+        It is guaranteed to be worst-case O(n log n) runtime.
+    """
+    if key is None:
+        try:
+            return _sync_builtins.sorted(iterable, reverse=reverse)
+        except TypeError:
+            pass
+    key = _awaitify(key) if key is not None else _identity
+    keyed_items = [(await key(item), item) async for item in aiter(iterable)]
+    keyed_items.sort(key=lambda ki: ki[0], reverse=reverse)
+    return [item for key, item in keyed_items]
diff --git a/docs/source/api/builtins.rst b/docs/source/api/builtins.rst
index 3032af9..fa48df7 100644
--- a/docs/source/api/builtins.rst
+++ b/docs/source/api/builtins.rst
@@ -61,3 +61,8 @@ Standard types
 
 .. autofunction:: tuple(iterable: (async) iter T = ()) -> (T, ...)
     :async:
+
+.. autofunction:: sorted(iterable: (async) iter T, *, key: (T) → (await) Any, reverse: bool) -> [T, ...]
+    :async:
+
+    .. versionadded:: 1.2.0


Test patch:
diff --git a/unittests/test_builtins.py b/unittests/test_builtins.py
index 500b638..776867e 100644
--- a/unittests/test_builtins.py
+++ b/unittests/test_builtins.py
@@ -1,3 +1,5 @@
+import random
+
 import pytest
 
 import asyncstdlib as a
@@ -253,3 +255,48 @@ async def test_types():
         zip((str(i) for i in range(5)), range(5)), b=3
     )
     assert await a.dict() == dict()
+
+
+sortables = [
+    [],
+    [0],
+    [1, 4, 17, -12, 3, 47, -98, 72, -1138],
+    list(range(20)),
+    list(range(2000)),
+    [random.random() for _ in range(2000)],
+]
+
+
+@pytest.mark.parametrize("sortable", sortables)
+@pytest.mark.parametrize("reverse", [True, False])
+@sync
+async def test_sorted_direct(sortable, reverse):
+    assert await a.sorted(sortable, reverse=reverse) == sorted(
+        sortable, reverse=reverse
+    )
+    assert await a.sorted(asyncify(sortable), reverse=reverse) == sorted(
+        sortable, reverse=reverse
+    )
+    assert await a.sorted(sortable, key=lambda x: x, reverse=reverse) == sorted(
+        sortable, key=lambda x: x, reverse=reverse
+    )
+    assert await a.sorted(
+        sortable, key=awaitify(lambda x: x), reverse=reverse
+    ) == sorted(sortable, key=lambda x: x, reverse=reverse)
+
+
+@sync
+async def test_sorted_stable():
+    values = [-i for i in range(20)]
+
+    def collision_key(x):
+        return x // 2
+
+    # test the test...
+    assert sorted(values, key=collision_key) != [
+        item for key, item in sorted([(collision_key(i), i) for i in values])
+    ]
+    # test the implementation
+    assert await a.sorted(values, key=awaitify(collision_key)) == sorted(
+        values, key=collision_key
+    )