Selection Sort

Algorithm:

• Find smallest element with linear scan
• Move it to the front
• Continue until all elements are in place

Time Complexity:

• Best: O(n2) - when the list is already sorted (https://stackoverflow.com/questions/43298396/best-case-time-complexity-for-selection-sort)
• Worst: O(n2) - when required to reverse the list

Space Complexity:

• O(1) - usually no extra space is required 

In-place: yes
Stable: yes

Python Implementation:
def selection_sort(arr):
    n = len(arr)
    for i range(n):
        min_index = i
        for j in range(i+1, n):
            if a[min_index] > a[j]:
                 min_index = j
    a[i], a[min_index] = a[min_index], a[i]