  In the matroid partitioning problem, we are given $k$ matroids $\mathcal{M}_1
= (V, \mathcal{I}_1), \dots , \mathcal{M}_k = (V, \mathcal{I}_k)$ defined over
a common ground set $V$ of $n$ elements, and we need to find a partitionable
set $S \subseteq V$ of largest possible cardinality, denoted by $p$. Here, a
set $S \subseteq V$ is called partitionable if there exists a partition $(S_1,
\dots , S_k)$ of $S$ with $S_i \in \mathcal{I}_i$ for $i = 1, \ldots, k$. In
1986, Cunningham [SICOMP 1986] presented a matroid partition algorithm that
uses $O(n p^{3/2} + k n)$ independence oracle queries, which was the previously
known best algorithm. This query complexity is $O(n^{5/2})$ when $k \leq n$.
  Our main result is to present a matroid partition algorithm that uses
$\tilde{O}(k'^{1/3} n p + k n)$ independence oracle queries, where $k' =
\min\{k, p\}$. This query complexity is $\tilde{O}(n^{7/3})$ when $k \leq n$,
and this improves upon the one of previous Cunningham's algorithm. To obtain
this, we present a new approach \emph{edge recycling augmentation}, which can
be attained through new ideas: an efficient utilization of the binary search
technique by Nguyen [2019] and Chakrabarty-Lee-Sidford-Singla-Wong [FOCS 2019]
and a careful analysis of the independence oracle query complexity. Our
analysis differs significantly from the one for matroid intersection
algorithms, because of the parameter $k$. We also present a matroid partition
algorithm that uses $\tilde{O}((n + k) \sqrt{p})$ rank oracle queries.
