Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 49 ยท Shapes and Combining

Sorting and Searching

Sort and search NumPy arrays quickly. Learn sort vs np.sort, argsort, axis sorting, lexsort, partition, searchsorted, argwhere and stable sorts.

Ranking scores, finding the top ten, sorting a table by one column, looking up which bin a value falls into: all of these are sorting and searching problems, and NumPy solves them without Python loops. The functions are fast because they run in compiled code, and they come in two flavors. Some return the sorted values, others return the indexes that would sort the data, which is far more flexible.

In this lesson you will sort along axes, sort by several keys, grab the top k values without a full sort, search a sorted array with binary search, and find positions where a condition holds. It assumes you are comfortable with indexing and boolean masks.

sort: values in order

There are two spellings, and the difference matters:

  • np.sort(a) returns a sorted copy and leaves a alone.
  • a.sort() sorts in place and returns None.

By default sorting works along the last axis, which means each row of a 2D array is sorted independently. Pass axis=0 to sort each column, or axis=None to flatten first.

Python np.sort, a.sort() and axes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Things to notice:

  • There is no reverse=True argument. For descending order, reverse the result with [::-1] (a view, so it is free) or sort the negated values.
  • Sorting a table row by row (axis=1, the default) does not keep rows together as records. Each row is reordered internally. If you want to reorder whole rows by some key, you need argsort (next section).
  • Strings sort by code point, so uppercase letters come before lowercase ones: Apple sorts ahead of banana here, but Zebra would also sort ahead of apple.
  • NaN values are sorted to the end.

argsort: the order, not the values

np.argsort(a) returns the indexes that would sort a. Used as an index, they sort any array of the same length in the same way. That is how you sort one array by another, the NumPy equivalent of "sort the names by their scores".

flowchart LR
    S["scores<br/>72 95 88 95 61"] --> A["argsort<br/>4 0 2 1 3"]
    A --> N["names[order]<br/>Eli Ana Cleo Ben Dev"]
    A --> R["scores[order]<br/>61 72 88 95 95"]

One index array reorders every parallel array the same way.

Python argsort for sorting by another array

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a 2D result of argsort(axis=1), plain m[idx] would not do what you want. Use np.take_along_axis(m, idx, axis=1) to apply per-row orderings. The "ranks" trick at the end inverts a permutation: ranks[order] = arange writes the rank of each item into its original position.

Notice the two descending variants: they differ for the tied scores (Ben and Dev both scored 95). Negating the values keeps Ben ahead of Dev, while reversing an ascending sort puts Dev first. Ties are the topic of the section on stability below.

Sorting by several keys with lexsort

np.lexsort sorts by more than one key and returns indexes. The surprising rule: the last key you pass is the primary key. To sort by last name, then by first name, write np.lexsort((first, last)).

Structured arrays, which have named fields, can be sorted with order= instead. They are introduced properly in Structured Arrays and Text Data.

Python lexsort and sorting structured data

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

To sort one key descending inside lexsort, negate it when it is numeric, as the score example shows. Strings cannot be negated; for those, rank them first (for example with the argsort ranking trick) and negate the ranks.

Stable sorts

A sort is stable when items that compare equal keep the order they had in the input. NumPy's default kind="quicksort" is not guaranteed to be stable. Pass kind="stable" when ties must keep their input order. This matters in a very practical technique: sort by the secondary key first, then by the primary key with a stable sort. The ties of the second pass remain ordered by the first.

Python Two-pass sorting with a stable sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result is grouped by city and alphabetical by name within each city, exactly as lexsort would give. Under the hood NumPy uses a merge-sort variant for stable sorts (and radix sort for small integer types).

partition: the top k without a full sort

Sorting a million numbers just to see the five smallest wastes work. np.partition(a, k) rearranges the array so that the element at position k is the one that would be there in the sorted array, everything before it is smaller or equal, and everything after it is larger or equal. The two sides are not sorted. np.argpartition returns the matching indexes.

Python partition and argpartition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because only the boundary is guaranteed, the order inside each side is unspecified. Sort just those few elements afterwards, as the last lines do. partition runs in linear time on average, versus n log n for a full sort, which is a real saving for large arrays when you only need a handful of extremes.

If an array is already sorted, you do not need to scan it. np.searchsorted(sorted_array, values) returns, for each value, the index where it would have to be inserted to keep the array sorted, using binary search. With side="left" (the default) an equal value goes before existing equal values, with side="right" after them.

This is also the way to bin continuous values: the cut points are the sorted array and the result is the bin number. (np.digitize, in the next lesson, is a close relative.)

Python searchsorted, bins and argwhere

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

searchsorted does not check that the array is sorted. On unsorted input it returns garbage without any error, so sort first or know your data.

The last block shows three ways to ask "where?":

  • np.argwhere(cond) returns an (n, ndim) array with one row of coordinates per match.
  • np.nonzero(cond) returns a tuple with one index array per axis, ready to use as an index.
  • np.flatnonzero(cond) returns positions in the flattened array.

argmax gives only the first position of the maximum; flatnonzero(vals == vals.max()) finds all ties.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a.sort() return?

    The method sorts the array itself and returns None. np.sort(a) is the version that returns a sorted copy.
  2. 2. How do you sort the array names by the values in scores?

    argsort returns the order that sorts scores, and indexing names with it applies the same reordering.
  3. 3. In np.lexsort((first, last)), which key is the primary sort key?

    lexsort treats the last key in the sequence as the primary one and earlier keys as tie-breakers.
  4. 4. Why use np.partition(data, k)[:k] instead of np.sort(data)[:k] for the k smallest values of a huge array?

    partition only guarantees the split around position k. It takes roughly linear time, and you can sort just the k values afterwards.
  5. 5. What must be true of the array passed to np.searchsorted?

    searchsorted does a binary search and does not verify the order. On unsorted data it silently returns wrong positions.

Summary

  • np.sort returns a sorted copy, a.sort() sorts in place; sorting is along the last axis by default, NaN goes last, and descending order is [::-1].
  • np.argsort gives indexes, which lets you sort parallel arrays together; use take_along_axis for per-row orders.
  • np.lexsort sorts by several keys with the last key as primary; use kind="stable" and multiple passes when ties must keep their order.
  • np.partition and np.argpartition find the k smallest or largest values without a full sort.
  • np.searchsorted is binary search on a sorted array and doubles as a binning tool; argwhere, nonzero and flatnonzero locate matches.

Next, find the distinct values and count them in Unique Values, Sets and Counting.