# Sorting Algorithms Implementations in Python

Sorting is one of the most used features in programming. And it will take time to complete the sorting if we didn’t use the correct algorithm.

In this article, we are going to discuss different sorting algorithms.

We will walk you through the different sorting algorithms with every step that comes in implementation. The implementation part will be in Python. You can easily convert it into any language once you get the algorithm. That’s the matter of language syntax.

We will see different algorithms from worst to best in this tutorial. So, don’t worry. Follow the article and implement them.

Let’s dive into the sorting algorithms.

## Insertion Sort

Insertion sort is one of the simple sorting algorithms. It’s easy to implement. And it will cost you more time to sort an array. It won’t be used in most of the cases for sorting for larger arrays.

The **insertion sort **algorithm maintains sorted and unsorted sub-parts in the given array.

The **sorted **sub-part contains only the first element at the beginning of the sorting process. We will take an element from the unsorted array and place them in the correct position in the sorted sub-array.

Let’s see the visual illustrations of **insertion sort **step by step with an example.

Let’s see the steps to implement the **insertion sort**.

- Initialize the array with dummy data (integers).
- Iterate over the given array from the second element.
- Take the current position and element in two variables.
- Write a loop that iterates until the first element of the array or the element occurs that is less than the current element.
- Update the current element with the previous element.
- Decrement of the current position.

- Here, the loop must reach either the start of the array or find a smaller element than the current element. Replace the current position element with the current element.

The time complexity of the **insertion sort **is **O(n^2),** and the space complexity if **O(1)**.

That’s it; we’ve sorted the given array. Let’s run the following code. I hope you have installed Python, if not check out the installation guide. Alternatively, you can use an online Python compiler.

```
def insertion_sort(arr, n):
for i in range(1, n):
## current position and element
current_position = i
current_element = arr[i]
## iteratin until
### it reaches the first element or
### the current element is smaller than the previous element
while current_position > 0 and current_element <
arr[current_position - 1]:
## updating the current element with previous element
arr[current_position] = arr[current_position - 1]
## moving to the previous position
current_position -= 1
## updating the current position element
arr[current_position] = current_element
if __name__ == '__main__':
## array initialization
arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
insertion_sort(arr, 9)
## printing the array
print(str(arr))
```

## Selection Sort

The selection sort is similar to the insertion sort with a slight difference. This algorithm also divides the array into sorted and unsorted sub-parts. And then, on each iteration, we will take the minimum element from the **unsorted sub-part **and place it in the last position of the **sorted sub-part**.

Let’s illustrations of **selection sort **for better understanding.

Let’s see the steps to implement the **selection sort**.

- Initialize the array with dummy data (integers).
- Iterate over the given array.
- Maintain the index of the minimum element.
- Write a loop that iterates from the current element to the last element.
- Check whether the current element is less than the minimum element or not.
- If the current element less than the minimum element, then replace the index.

- We have the minimum element index with us. Swap the current element with the minimum element using the indexes.

The time complexity of the **selection sort **is **O(n^2),** and the space complexity if **O(1)**.

Try to implement the algorithm as it is similar to the **insertion sort**. You can see the code below.

```
def selection_sort(arr, n):
for i in range(n):
## to store the index of the minimum element
min_element_index = i
for j in range(i + 1, n):
## checking and replacing the minimum element index
if arr[j] < arr[min_element_index]:
min_element_index = j
## swaping the current element with minimum element
arr[i], arr[min_element_index] = arr[min_element_index], arr[i]
if __name__ == '__main__':
## array initialization
arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
selection_sort(arr, 9)
## printing the array
print(str(arr))
```

## Bubble Sort

Bubble sort is a simple algorithm. It swaps the adjacent elements on each iteration repeatedly until the given array is sorted.

It iterates over the array and moves the current element to the next position until it is less than the next element.

Illustrations help us understand the **bubble sort **visually. Let’s see them.

Let’s see the steps to implement the **bubble sort**.

- Initialize the array with dummy data (integers).
- Iterate over the given array.
- Iterate from
**0**to**n-i-1**. The last**i**elements are already sorted.- Check whether the current element is greater than the next element or not.
- If the current element is greater than the next element, then swap the two elements.

- Iterate from

The time complexity of the **bubble sort **is **O(n^2),** and the space complexity if **O(1)**.

You can easily implement the bubble sort by now. Let’s see the code.

```
def bubble_sort(arr, n):
for i in range(n):
## iterating from 0 to n-i-1 as last i elements are already sorted
for j in range(n - i - 1):
## checking the next element
if arr[j] > arr[j + 1]:
## swapping the adjucent elements
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if __name__ == '__main__':
## array initialization
arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
bubble_sort(arr, 9)
## printing the array
print(str(arr))
```

## Merge Sort

Merge sort is a recursive algorithm to sort the given array. It’s more efficient than the previously discussed algorithms in terms of time complexity. It follows the divide and conquers approach.

The merge sort algorithm divides the array into two halves and sorts them separately. After sorting the two halves of the array, it merges them into a single sorted array.

As it’s a recursive algorithm, it divides the array till the array becomes the simplest (array with one element) one to sort.

It’s time for illustration. Let’s see it.

Let’s see the steps to implement the **merge sort**.

- Initialize the array with dummy data (integers).
- Write a function called
**merge**to merge sub-arrays into a single sorted array. It accepts the arguments array, left, mid, and right indexes.- Get the lengths of left and right sub-arrays lengths using the given indexes.
- Copy the elements from the array into the respective left and right arrays.
- Iterate over the two sub-arrays.
- Compare the two sub-arrays elements.
- Replace the array element with the smaller element from the two sub-arrays for sorting.

- Check whether any elements are remaining in both the sub-arrays.
- Add them to the array.

- Write a function called
**merge_sort**with parameters array, left and right indexes.- If the left index is greater than or equal to the right index, then return.
- Find the middle point of the array to divide the array into two halves.
- Recursively call the
**merge_sort**using the left, right, and mid indexes. - After the recursive calls, merge the array with the
**merge**function.

The time complexity of the **merge sort **is **O(nlogn),** and the space complexity if **O(1)**.

That’s it for the merge sort algorithm implementation. Check the code below.

```
def merge(arr, left_index, mid_index, right_index):
## left and right arrays
left_array = arr[left_index:mid_index+1]
right_array = arr[mid_index+1:right_index+1]
## getting the left and right array lengths
left_array_length = mid_index - left_index + 1
right_array_length = right_index - mid_index
## indexes for merging two arrays
i = j = 0
## index for array elements replacement
k = left_index
## iterating over the two sub-arrays
while i < left_array_length and j < right_array_length:
## comapring the elements from left and right arrays
if left_array[i] < right_array[j]:
arr[k] = left_array[i]
i += 1
else:
arr[k] = right_array[j]
j += 1
k += 1
## adding remaining elements from the left and right arrays
while i < left_array_length:
arr[k] = left_array[i]
i += 1
k += 1
while j < right_array_length:
j += 1
k += 1
def merge_sort(arr, left_index, right_index):
## base case for recursive function
if left_index >= right_index:
return
## finding the middle index
mid_index = (left_index + right_index) // 2
## recursive calls
merge_sort(arr, left_index, mid_index)
merge_sort(arr, mid_index + 1, right_index)
## merging the two sub-arrays
merge(arr, left_index, mid_index, right_index)
if __name__ == '__main__':
## array initialization
arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
merge_sort(arr, 0, 8)
## printing the array
print(str(arr))
```

### Conclusion

There are many other sorting algorithms, but above are some of the frequently used. Hope you enjoyed learning the sorting.

Next, find out about search algorithms.

Happy Coding 🙂 👨💻