PHASE 4Beginner ~28 min· topic 2 of 11

Topic 4.2

Slicing, Sorting and Searching Lists

In one line

A slice items[start:stop:step] takes a part of a list as a new list, and you can also assign to a slice to change many items at once. sorted() returns a new sorted list, sort() reorders in place, and key= chooses what to sort by.

Think of it like this

A deck of numbered cards laid out in a row. You can pick up cards 3 to 6 as a small pile (a slice), swap that stretch for other cards, line the cards up from smallest to largest (sorting), or ask for the lowest and highest card. Python lists support all of this with very little code.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Slice: A part of a list taken with items[start:stop:step]. The result is a new list.
Start, stop, step: Where a slice begins (included), where it ends (not included), and how far it moves each time.
sorted(): A built-in that returns a new, sorted list from any collection.
sort(): A list method that sorts the list itself, in place, and returns None.
key: A function that turns each item into the value used for comparing. It is called once per item.
Stable sort: A sort that keeps equal items in their original order.
Ascending / descending: Smallest first / largest first.
Binary search: Finding a value in an already sorted list by repeatedly looking at the middle and discarding half.

Step by step

01Slices: start included, stop excluded

Think of the numbers as pointing at the gaps before each item. [1:4] means "from the gap before index 1 to the gap before index 4", which contains indexes 1, 2 and 3. A handy fact: items[:n] gives exactly n items (if the list is long enough), and items[:n] + items[n:] is always the whole list.

main.pywhole filepython

nums = [10, 20, 30, 40, 50, 60]

print(nums[1:4])    # [20, 30, 40]
print(nums[:3])     # [10, 20, 30]
print(nums[3:])     # [40, 50, 60]
print(nums[-2:])    # [50, 60]

Slices: start included, stop excludeddiagram

Rendering diagram…

02Step and reversing

The third number is the step. [::2] starts at the beginning and takes every second item. A step of -1 walks from the end to the start, so [::-1] is the usual way to make a reversed copy of a list or a string.

main.pywhole filepython

nums = [10, 20, 30, 40, 50, 60]

print(nums[::2])    # [10, 30, 50]
print(nums[::-1])   # [60, 50, 40, 30, 20, 10]
print(nums[2:100])  # no error: [30, 40, 50, 60]

03Change many items at once with slice assignment

When a slice is on the left of =, you replace that stretch of the list. The replacement can be shorter or longer, so the list can shrink or grow. del nums[0:2] removes a stretch. An empty slice such as nums[2:2] is a spot to insert into.

main.pywhole filepython

nums = [10, 20, 30, 40, 50]
nums[1:3] = [21, 22, 23]    # two items replaced by three
del nums[0:2]               # remove a stretch
nums[1:1] = [99]            # insert at index 1

04sorted() makes a new list, sort() changes the old one

Use sorted when you need to keep the original or when you have a tuple, a set, or a dictionary (Topics 4.3, 4.4 and 4.6 teach those three; sorted accepts them all). Use .sort() when you own the list and don't need the old order. Remember that .sort() returns None.

main.pywhole filepython

scores = [72, 95, 88, 61]
best_first = sorted(scores, reverse=True)
print(best_first)    # [95, 88, 72, 61]
print(scores)        # still [72, 95, 88, 61]

scores.sort()
print(scores)        # [61, 72, 88, 95]

05Sort by a key

Without a key, Python compares the items themselves. For text, capital letters sort before small ones, so "Zoe" comes before "adam". With key=str.lower each word is lowered only for comparing; the list still holds the original words.

main.pywhole filepython

names = ["adam", "Zoe", "Bob"]
print(sorted(names))                  # ['Bob', 'Zoe', 'adam']
print(sorted(names, key=str.lower))   # ['adam', 'Bob', 'Zoe']
print(sorted(names, key=len))         # by length

06Stable sorting for two-level order

Because equal items keep their order, you can sort by the secondary field first and the primary field last. Here the words are first put in alphabetical order, then sorted by length: the result is by length, and alphabetical inside each length.

main.pywhole filepython

words = ["pear", "fig", "apple", "kiwi", "date"]
step1 = sorted(words)               # alphabetical
step2 = sorted(step1, key=len)      # then by length (stable)
print(step2)

07min, max, sum and a first look at bisect

min, max and sum walk the list once. For a list that is already sorted, the bisect module finds where a value belongs. (A module is a ready-made toolbox of extra code that comes with Python. The line import bisect brings the toolbox in; Topic 6.1 teaches import, so for now copy the line as it is.) bisect halves the search range each time, so it needs only about 20 steps for a million items. bisect_left returns the index where the value is, or would be inserted. The DSA course explains the idea of binary search in depth (/dsa).

main.pywhole filepython

import bisect

scores = sorted([72, 95, 88, 61])
print(min(scores), max(scores), sum(scores))
print(bisect.bisect_left(scores, 88))   # index of 88
bisect.insort(scores, 80)               # insert and stay sorted

Try it yourself

1
Predict slices
For nums = [10, 20, 30, 40, 50, 60], work out nums[2:5], nums[-3:-1] and nums[::3] on paper. Then type them into the first example and run it.
2
Change the key
In the second example, add a new last line: print(sorted(words, key=str.upper)). Run it, then add , reverse=True before the closing bracket and run again. Which output is different from the plain sorted(words) line, and why? (Sorting by something like the last letter needs a small function you write yourself. Phase 5 teaches how, and Topic 5.6 shows it with key=.)

Code & diagrams

Slices in action New tab

Change the numbers in the brackets and predict each result first.

Expected output

nums[1:4]   [20, 30, 40]
nums[:3]    [10, 20, 30]
nums[3:]    [40, 50, 60]
nums[-2:]   [50, 60]
nums[::2]   [10, 30, 50]
nums[::-1]  [60, 50, 40, 30, 20, 10]
nums[2:100] [30, 40, 50, 60]
copy: [999, 20, 30, 40, 50, 60]
original: [10, 20, 30, 40, 50, 60]
after slice assignment: [10, 21, 22, 23, 40, 50, 60]
after del: [22, 23, 40, 50, 60]

sort, sorted, key and stability New tab

Expected output

sorted: ['Apple', 'banana', 'cherry', 'date', 'fig']
by length: ['fig', 'date', 'Apple', 'banana', 'cherry']
ignore case: ['Apple', 'banana', 'cherry', 'date', 'fig']
reverse: ['fig', 'date', 'cherry', 'banana', 'Apple']
original: ['banana', 'Apple', 'cherry', 'date', 'fig']
sort() returned: None
words now: ['Apple', 'banana', 'cherry', 'date', 'fig']
by length, ties keep order: ['fig', 'pear', 'kiwi', 'date', 'apple']
two levels: ['fig', 'date', 'kiwi', 'pear', 'apple']

min, max, sum and bisect New tab

Expected output

min: 61
max: 95
sum: 395
average: 79.0
longest word: notebook
ordered: [61, 72, 79, 88, 95]
88 is at index 3
after insort(80): [61, 72, 79, 80, 88, 95]

Rank orders: two passes with a stable sort New tab

A shop wants the biggest orders first, and customers in alphabetical order when two orders are equal. `itemgetter(1)` is a ready-made recipe for "take item 1 of each tuple" (Topic 5.6 explains `key=`; Topic 6.1 explains the import).

Expected output

by customer: [('Asha', 450), ('Asha', 90), ('Meena', 450), ('Ravi', 1200)]
biggest first, ties by customer: [('Ravi', 1200), ('Asha', 450), ('Meena', 450), ('Asha', 90)]
original untouched: [('Meena', 450), ('Asha', 450), ('Ravi', 1200), ('Asha', 90)]

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Sort numbers and text together

Put a string inside a list of numbers and sort it.

main.pywhole filepython

items = [3, "a", 1]
print(sorted(items))

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 2, in <module>

print(sorted(items))

~~~~~~^^^^^^^

TypeError: '<' not supported between instances of 'str' and 'int'

Break #2

Use the result of sort()

Assign the result of .sort() to a name and use it.

main.pywhole filepython

numbers = [3, 1, 2]
numbers = numbers.sort()
print(numbers[0])

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 3, in <module>

print(numbers[0])

~~~~~~~^^^

TypeError: 'NoneType' object is not subscriptable

Myth vs fact

Myth

items[1:4] includes index 4.

Fact

The stop index is never included. items[1:4] has indexes 1, 2 and 3: exactly stop - start items.

Myth

A slice that goes past the end raises an error.

Fact

Slices clip silently to the list: items[2:100] is fine. Only single-index access such as items[100] raises IndexError.

Myth

sorted() changes the list it is given.

Fact

It never does. It returns a new list. Only .sort() changes a list.

Myth

Sorting twice destroys the first sort.

Fact

Because the sort is stable, sorting by a second key keeps the first order among equal items. That is a feature you can use on purpose.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
CPython's sort is Timsort: a hybrid of merge sort and insertion sort that finds runs already in order (since Python 3.11 it decides which runs to merge with the "powersort" rule, but the idea and the guarantees are the same). It takes O(n log n) in the worst case and close to O(n) on data that is already nearly sorted, and it is stable. The key function is called exactly once per item (the results are cached), so an expensive key is cheaper than an expensive comparison. Even reverse=True keeps the sort stable: ties stay in their original order, they are not flipped (the last example below shows it).
▸
Slicing copies pointers, not items, so items[:] of a million-item list is fast but still O(n) and uses memory for a million pointers. For a huge list where you only need to walk a part, itertools.islice (Topic 9.4) avoids the copy. Slice assignment with a step is stricter than a plain slice: nums[::2] = [0] raises ValueError: attempt to assign sequence of size 1 to extended slice of size 3, because an extended slice cannot change the length of the list.
▸
bisect assumes the list is already sorted and does not check; on unsorted data it returns nonsense without any error. insort finds the spot in O(log n) but still has to shift items, so each insertion is O(n). For a continuously growing sorted collection a heap (heapq) or a balanced tree structure fits better. Since Python 3.10 the bisect functions also take key=, so you can search a list of records without building a separate list of keys. Remember that min() and max() of an empty list raise ValueError; pass default= when empty is possible.
▸
Sorting strings uses Unicode code points, not a dictionary's idea of order: "Zoe" sorts before "adam", and accented letters sort after "z". For human-friendly order in other languages use locale-aware tools. In AI work, you meet sorted(..., key=..., reverse=True) constantly to rank results by score.

Remember this

1
A slice is written items[start:stop]. It gives a new list holding the items from index start up to, but not including, stop. So [10, 20, 30, 40, 50][1:4] is [20, 30, 40]. A way to remember: the numbers point at the gaps between items, and the slice is what lies between two gaps. Leave out start to begin at the start and leave out stop to go to the end: items[:3] and items[3:].
2
A third number is the step: items[::2] takes every second item, and items[::-1] walks backwards, which makes a reversed copy. Negative numbers count from the end: items[-2:] is the last two items. Slices never raise IndexError: if the numbers are too large, Python quietly stops at the edge, so items[2:100] is fine.
3
Because a slice is a new list, items[:] is a quick way to copy a whole list (a shallow copy; Topic 4.9 explains what that means). You can also assign to a slice: items[1:3] = [21, 22, 23] replaces two items with three, and the list grows. del items[0:2] removes a stretch. The replacement may be a different length than the part it replaces.
4
sorted(items) returns a new sorted list and leaves items alone. items.sort() sorts the list in place and returns None. Both put the smallest first; reverse=True puts the largest first. A list of mixed types such as numbers and strings cannot be sorted, because Python does not know how to compare them, and raises TypeError.
5
To sort by something other than the item itself, pass key=, a function that is called once for each item to produce the value to sort by. sorted(words, key=len) sorts by length. sorted(words, key=str.lower) ignores capital letters. Passing functions around is explained in Topic 5.6, so for now treat key=len and key=str.lower as ready-made recipes.
6
Python's sort is stable: items that compare equal keep the order they had before. That lets you sort in two passes (first by the less important field, then by the more important one) and get a correct two-level order. min(items), max(items) and sum(items) give the smallest, the largest and the total; min and max also accept key=. sorted, min and max work on any collection, not only lists.

Explain it without notes

How does a slice like items[1:4:2] work, and what does it return?

What is the difference between sorted(items) and items.sort()?

What does a stable sort mean, and why is it useful?

What does the key argument do, and how many times is it called?

Practice

Given nums = [5, 3, 8, 1, 9, 2], print the first three items, the last two items, every second item, and the list in reverse. Do not change nums.

Sort names = ["mona", "Raj", "amit", "Zoya"] in a way that ignores capital letters and print the result. Print names afterwards to show it is unchanged.

Given scores = [72, 95, 88, 61], print the highest score, the lowest score and the average, and the three highest scores from best to worst.

Trade-offs

↔
Sorting once and searching many times pays off. Sorting costs O(n log n), and each bisect lookup then costs O(log n). If you search only once, a plain scan (O(n)) is cheaper than sorting first.
↔
**sorted() costs memory, .sort() costs the original order.** A new list needs room for n pointers; sorting in place needs almost none but destroys the old order and surprises any other code that holds the same list.

Done when you can

Done when you can predict items[a:b], items[::k] and items[::-1] for a small list.
Done when you can replace and delete a stretch of a list with slice assignment and del.
Done when you can choose between sorted() and .sort() and say what each returns.
Done when you can sort by length or ignore case using key=, and say what stable means.
Done when you can use min, max and sum, and explain when bisect helps.

Command Palette

Words you'll meet

Step by step

01Slices: start included, stop excluded

02Step and reversing

03Change many items at once with slice assignment

04sorted() makes a new list, sort() changes the old one

05Sort by a key

06Stable sorting for two-level order

07min, max, sum and a first look at bisect

Try it yourself

Predict slices

Change the key

Code & diagrams

Break it on purpose

Sort numbers and text together

Use the result of sort()

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can