Different Sorting Methodologies

Different Sorting Methodologies
Introduction

Sorting is one of the most important operations in computer science. Sorting means arranging elements in a particular order, usually ascending or descending order. Sorting is used in searching, data analysis, databases, and many real-world applications.

In this blog, we will discuss the different sorting algorithms taught in the session, their working methods, and time complexities.

1. Bubble Sort Concept

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. The largest element “bubbles up” to the end of the array after each pass.

Steps

Compare first and second element

If first > second → swap

Move to next pair

Repeat for entire array

After each pass, largest element moves to the end

Repeat until array is sorted

Python Code
arr = [5, 3, 8, 4, 2]

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]

print(arr)
Time Complexity
Case Time
Best O(n)
Average O(n²)
Worst O(n²)

1. Selection Sort Concept

Selection Sort repeatedly selects the smallest element from the unsorted part and places it at the beginning.

Steps

Find smallest element in array

Swap with first element

Find next smallest

Swap with second element

Repeat until sorted

Python Code
arr = [5, 3, 8, 4, 2]

n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]

print(arr)
Time Complexity
Case Time
Best O(n²)
Average O(n²)
Worst O(n²)

1. Insertion Sort Concept

Insertion Sort works like sorting playing cards. It picks one element and inserts it into the correct position in the sorted part of the array.

Steps

Start from second element

Compare with previous elements

Shift larger elements to the right

Insert element in correct position

Repeat

Python Code
arr = [5, 3, 8, 4, 2]

for i in range(1, len(arr)):
key = arr[i]
j = i - 1

while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]
    j -= 1

arr[j + 1] = key

print(arr)
Time Complexity
Case Time
Best O(n)
Average O(n²)
Worst O(n²)

1. Merge Sort Concept

Merge Sort uses Divide and Conquer technique.

Divide array into two halves

Sort each half

Merge sorted halves

Steps

Divide array into two halves

Recursively sort both halves

Merge the sorted halves

Repeat until sorted

Python Code
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
left = arr[:mid]
right = arr[mid:]

    merge_sort(left)
    merge_sort(right)

    i = j = k = 0

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

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

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

arr = [5, 3, 8, 4, 2]
merge_sort(arr)
print(arr)
Time Complexity
Case Time
Best O(n log n)
Average O(n log n)
Worst O(n log n)

1. Quick Sort Concept

Quick Sort selects a pivot element and partitions the array so that:

Elements smaller than pivot → left

Elements greater than pivot → right

Python Code
def quick_sort(arr):
if len(arr) <= 1:
return arr

pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

arr = [5, 3, 8, 4, 2]
print(quick_sort(arr))
Time Complexity
Case Time
Best O(n log n)
Average O(n log n)
Worst O(n²)
Comparison Table
Algorithm Best Average Worst
Bubble Sort O(n) O(n²) O(n²)
Selection Sort O(n²) O(n²) O(n²)
Insertion Sort O(n) O(n²) O(n²)
Merge Sort O(n log n) O(n log n) O(n log n)
Quick Sort O(n log n) O(n log n) O(n²)
Conclusion

Sorting algorithms are very important in programming and problem solving.

Bubble Sort – Simple but slow

Selection Sort – Simple but inefficient

Insertion Sort – Good for small datasets

Merge Sort – Efficient and stable

Quick Sort – Very fast in practice

For large datasets, Merge Sort and Quick Sort are preferred.