Sort

Stable Sort: Stable sort is a sorting algorithm that preserves the relative order of equal elements in the sorted output.
Local Sort: Local sort is a sorting algorithm that sorts elements in a small region of the list.

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Stable Sort: Yes
Local Sort: Yes

1
2
Time complexity: O(n^2)
Space complexity: O(1)

Here is the implementation of bubble sort in Python:

1
2
3
4
5
6
7
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Selection Sort

Selection sort is another simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the list and putting it at the beginning. The pass through the list is repeated until the list is sorted.

Stable Sort: Yes
Local Sort: Yes

1
2
Time complexity: O(n^2)
Space complexity: O(1)

Here is the implementation of selection sort in Python:

1
2
3
4
5
6
7
8
9
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Stable Sort: Yes
Local Sort: Yes

1
2
Time complexity: O(n^2)
Space complexity: O(1)

Here is the implementation of insertion sort in Python:

1
2
3
4
5
6
7
8
9
10
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

Merge Sort

Merge sort is a divide and conquer algorithm that divides the list into two halves, sorts each half recursively, and then merges the two sorted halves back together.

Stable Sort: Yes
Local Sort: No

1
2
Time complexity: O(nlogn)
Space complexity: O(n)

Here is the implementation of merge sort in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

    return arr

Quick Sort

Quick sort is a divide and conquer algorithm that selects a pivot element and partitions the other elements into two sub-lists, according to whether they are less than or greater than the pivot. The sub-lists are then sorted recursively.

Stable Sort: No
Local Sort: Yes

1
2
Time complexity: O(nlogn)
Space complexity: O(logn)

Here is the implementation of quick sort in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quick_sort(left) + [pivot] + quick_sort(right)