Keeping things sorted with bisect.insort()

Don’t Repeat Yourself. If you find yourself sorting large lists again and again using the .sort() or sorted() methods you’re probably doing it wrong, but unless you’re working on large lists you’re probably not noticing it (I’d argue if you know you’re definitely not going to be working on large lists then using bisect.insort() might be overkill).

bisect.insort() allows us to use array bisection to efficiently insert an element into an already sorted array.

To compare speeds I created a simple script to sort the same list of random integers using bisect.insort() and list.sort().

#!/usr/bin/env python3

import logging as log
import utils.dummydata as dummy
from utils.timing import timed
import bisect

LIST_SIZE = 10**5 # 100,000

def setup():
    setup_logging()

def setup_logging():
    logging_format = "%(asctime)s: %(message)s"
    log.basicConfig(
        format=logging_format,
        level=log.DEBUG,
        datefmt="%H:%M:%S"
    )

@timed
def basic_sort(vals: list[int]) -> list[int]:

    new_list : list[int] = []

    for v in vals:
        new_list.append(v)
        new_list.sort()
    
    return new_list

@timed
def insort_sort(vals: list[int]) -> list[int]:
    
    new_list : list[int] = []

    for v in vals: 
        bisect.insort(new_list, v)

    return new_list

def main():
    setup()

    random_nums = dummy.random_list(int, LIST_SIZE)

    log.info(f"Built a random list of {LIST_SIZE:,} ints")

    log.info("Building new sorted list using `list.sort()`...")
    basic_sort(random_nums)

    log.info("Building a new sorted list using `bisect.insort()`...")
    insort_sort(random_nums)
    

if __name__ == "__main__":
    main()

Output:

❯ ./main.py
 23:55:23: Built a random list of 100,000 ints
 23:55:23: Building new sorted list using list.sort()…
 23:56:10: Completed basic_sort in 47.511071838 seconds
 23:56:10: Building a new sorted list using bisect.insort()…
 23:56:12: Completed insort_sort in 1.136234315000003 seconds

That’s a 42x speed increase!