Returns a new array that lists the receiving array’s elements in ascending order as defined by the comparison function `comparator`

.

SDKs

- iOS 2.0+
- macOS 10.0+
- tvOS 9.0+
- watchOS 2.0+

Framework

- Foundation

## Declaration

## Discussion

The new array contains references to the receiving array’s elements, not copies of them.

This method is similar to `sorted`

, except that it uses the supplied hint to speed the sorting process. When you know the array is nearly sorted, this method is faster than `sorted`

. If you sorted a large array (`N`

entries) once, and you don’t change it much (`P`

additions and deletions, where `P`

is much smaller than `N`

), then you can reuse the work you did in the original sort by conceptually doing a merge sort between the `N`

“old” items and the `P`

“new” items.

To obtain an appropriate hint, use `sorted`

. You should obtain this hint when the original array has been sorted, and keep hold of it until you need it, after the array has been modified. The hint is computed by `sorted`

in `O(N)`

(where `N`

is the number of items). This assumes that items in the array implement a `-hash`

method. Given a suitable hint, and assuming that the hash function is a “good” hash function, -`sorted`

sorts the array in `O(P*LOG(P)+N)`

where `P`

is the number of adds or deletes. This is an improvement over the un-hinted sort, `O(N*LOG(N))`

, when `P`

is small.

The hint is simply an array of size `N`

containing the `N`

hashes. To re-sort you need internally to create a map table mapping a hash to the index. Using this map table on the new array, you can get a first guess for the indexes, and then sort that. For example, a sorted array {A, B, D, E, F} with corresponding hash values {25, 96, 78, 32, 17}, may be subject to small changes that result in contents {E, A, C, B, F}. The mapping table maps the hashes {25, 96, 78, 32, 17} to the indexes {#0, #1, #2, #3, #4}. If the hashes for {E, A, C, B, F} are {32, 25, 99, 96, 17}, then by using the mapping table you can get a first order sort {#3, #0, ?, #1, #4}, so therefore create an initial semi-sorted array {A, B, E, F}, and then perform a cheap merge sort with {C} that yields {A, B, C, E, F}.