Sorting and Searching in Python

Sorting arranges items in order (e.g., ascending), while searching finds an element’s position or presence in a collection.

lst = [3, 1, 2]
lst.sort()            # In‐place
sorted_lst = sorted(lst)  # Returns new list

lst.sort(reverse=True)
# or
sorted_lst = sorted(lst, reverse=True)

lst = ["banana","Apple","cherry"]
lst.sort(key=str.lower)

O(n log n), using Timsort.

if x in lst:
    print("Found")

A sequential scan through a list: O(n) time complexity.

def linear_search(arr, target):
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1

Repeatedly divide a sorted list in half to locate an element: O(log n).

def binary_search(arr, target, lo=0, hi=None):
    if hi is None: hi = len(arr)-1
    if lo > hi: return -1
    mid = (lo+hi)//2
    if arr[mid] == target: return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid+1, hi)
    else:
        return binary_search(arr, target, lo, mid-1)

def binary_search(arr, target):
    lo, hi = 0, len(arr)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if arr[mid] == target: return mid
        if arr[mid] < target:
            lo = mid+1
        else:
            hi = mid-1
    return -1

For binary search or any divide‐and‐conquer search on arrays.

list.sort() sorts in‐place and returns None; sorted() returns a new sorted list.

idx = min(range(len(lst)), key=lambda i: lst[i])

data.sort(key=lambda x: (x.age, x.name))

Python’s Timsort is stable by default.

Repeatedly pick the minimum element and swap to front: O(n²).

def selection_sort(a):
    n = len(a)
    for i in range(n):
        min_i = i
        for j in range(i+1, n):
            if a[j] < a[min_i]: min_i = j
        a[i], a[min_i] = a[min_i], a[i]

Repeatedly swap adjacent out‐of‐order elements: O(n²).

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        for j in range(0, n-i-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]

Build sorted list by inserting each element in place: O(n²) average.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i-1
        while j>=0 and a[j] > key:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key

Divide‐and‐conquer: split, sort halves, merge: O(n log n).

def merge_sort(a):
    if len(a)<=1: return a
    mid = len(a)//2
    left = merge_sort(a[:mid])
    right= merge_sort(a[mid:])
    return merge(left,right)

def merge(l, r):
    res=[]; i=j=0
    while i<len(l) and j<len(r):
        if l[i]<r[j]:
            res.append(l[i]); i+=1
        else:
            res.append(r[j]); j+=1
    res += l[i:]+r[j:]
    return res

Partition around pivot, recursively sort partitions: average O(n log n).

def quick_sort(a):
    if len(a)<=1: return a
    pivot = a[len(a)//2]
    left = [x for x in a if x<pivot]
    mid  = [x for x in a if x==pivot]
    right= [x for x in a if x>pivot]
    return quick_sort(left)+mid+quick_sort(right)

Build a heap then extract max repeatedly: O(n log n).

import heapq
a = [3,1,2]
heapq.heapify(a)  # in‐place
sorted_list = [heapq.heappop(a) for _ in range(len(a))]

Use heapq.nsmallest(k, a)[-1] or Quickselect: average O(n).

Partition‐based selection algorithm: average O(n), worst O(n²).

import random
def quickselect(a, k):
    if len(a)==1: return a[0]
    pivot = random.choice(a)
    lows = [x for x in a if x<pivot]
    highs= [x for x in a if x>pivot]
    eqs  = [x for x in a if x==pivot]
    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows)+len(eqs):
        return pivot
    else:
        return quickselect(highs, k-len(lows)-len(eqs))

For small integer ranges: count frequencies then output: O(n + k).

When range of input values (k) is not much larger than n.

Digit‐by‐digit sorting using stable sort (like counting sort): O(d·(n + k)).

Distribute into buckets then sort each: average O(n + k).

Modified binary search checking halves: O(log n).

def search_rotated(a, target):
    lo,hi=0,len(a)-1
    while lo<=hi:
        mid=(lo+hi)//2
        if a[mid]==target: return mid
        if a[lo]<=a[mid]:
            if a[lo]<=target<a[mid]: hi=mid-1
            else: lo=mid+1
        else:
            if a[mid]<target<=a[hi]: lo=mid+1
            else: hi=mid-1
    return -1

Like binary but probes based on value distribution: average O(log log n), worst O(n).

Find range by doubling then binary search: O(log n).

Start top‑right and move left/down: O(m + n).

Use merge sort on linked lists: O(n log n), O(1) extra space.

Sorting data larger than memory via chunking, sorting chunks, then k‑way merge.

Deterministic pivot for Quickselect: guarantees O(n) worst‑case.

Use two heaps (max‑heap for lower half, min‑heap for upper half).

import heapq
class MedianFinder:
    def __init__(self):
        self.small, self.large = [],[]
    def addNum(self, num):
        heapq.heappush(self.small, -num)
        if self.small and self.large and -self.small[0]>self.large[0]:
            val=-heapq.heappop(self.small)
            heapq.heappush(self.large,val)
        if len(self.small)>len(self.large)+1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large)>len(self.small)+1:
            heapq.heappush(self.small, -heapq.heappop(self.large))
    def findMedian(self):
        if len(self.small)>len(self.large):
            return -self.small[0]
        if len(self.large)>len(self.small):
            return self.large[0]
        return (-self.small[0]+self.large[0])/2

Merge k sorted lists using a min‑heap: O(n log k).

Find peak by binary search then search both halves: O(log n).

Use min‑heap of size k+1: O(n log k).

Three‑way partition in one pass: O(n).

def dutch_flag(a, pivot):
    low, mid, high = 0, 0, len(a)-1
    while mid<=high:
        if a[mid]<pivot:
            a[low],a[mid]=a[mid],a[low]; low+=1; mid+=1
        elif a[mid]>pivot:
            a[mid],a[high]=a[high],a[mid]; high-=1
        else:
            mid+=1

BST augmented with subtree sizes to select k‑th element in O(log n).

Use bit‑operations to optimize certain searches (e.g., next greater element via stack).

Place each number at its index: O(n), O(1) space.

First binary‑search peak, then binary‑search both ascending and descending sides.

Process bits one by one (MSB to LSB) grouping zeros and ones: O(n·w).

Find longest increasing subsequence in O(n log n) by building piles.

Character‑by‑character traversal: O(m) for word length m.

Data‑structure technique to speed multiple related binary searches.

External merge sort with multi‑pass k‑way merge.

Modified binary search skipping empty entries.

Hybrid quicksort‑heapsort: begins with quicksort, switches to heapsort on bad pivots.

Python’s built‑in stable sort combining merge sort and insertion sort.

Binary search over suffixes: O(m log n).

Doubling algorithm in O(n log n).

data.sort(key=lambda o: o.attr)

import bisect
pos = bisect.bisect_left(a, x)

O(log n) for insertion/search.

Use bisect.insort() for O(n) insertion but constant lookup.

Use deque to track minima in O(n).

Use heapq.nsmallest with key=distance.

Binary search prefix bounds then scan.

Speed up multi‑list searches by linking structures.

Use locale.strxfrm as key.

Timsort with galloping mode on runs.

Use binary search plus neighbor checks or BK‑trees for edit distance.