How to find kth smallest number in a list in Python

Overview

To find the $k^{th}$ smallest element in a list in Python, we use sorting algorithms.

Procedure and example

Through a sorting algorithm, we can sort a list and then, with the help of indexing, retrieve the $k^{th}$ element from the list. We can use any sorting algorithm. Here we’ll use the merge sort, which is a divide and conquer approach and has a time complexity of $O(nlog(n))$ .

def merge_sort(array):
    if len(array) > 1:
        r = len(array)//2
        L = array[:r]
        M = array[r:]
        merge_sort(L)
        merge_sort(M)
        i = j = k = 0
        while i < len(L) and j < len(M):
            if L[i] < M[j]:
                array[k] = L[i]
                i += 1
            else:
                array[k] = M[j]
                j += 1
            k += 1
        while i < len(L):
            array[k] = L[i]
            i += 1
            k += 1
        while j < len(M):
            array[k] = M[j]
            j += 1
            k += 1
    return array
# Return kth (k=3) smallest element from the list
def main():
  arr = [6, 5, 12, 10, 9, 1]
  arr = merge_sort(arr)
  k = 3
  print("kth (k=3) smallest element:",arr[k-1])
main()