Sorting Algorithms
Sorting is one of the most common operations performed by computers. It involves arranging data —
such as numbers or names — in a meaningful order (e.g., ascending or descending). Efficient sorting
helps in faster searching, data organization, and optimizing other algorithms.
Types of Sorting
There are several sorting algorithms, each with different approaches and efficiency characteristics.
Common sorting algorithms include:
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Quick Sort
Complexity of Sorting Algorithms
The complexity of a sorting algorithm generally refers to the time it takes to sort n items and is usually
measured by counting comparisons between elements.
The key operations involved in sorting can be summarized as:
1. Comparisons – Checking if one element is less than or greater than another.
2. Interchanges – Swapping positions of elements.
3. Assignments – Moving or copying elements to new positions.
Most complexity analyses focus on the number of comparisons, since other operations are often
proportional to this number.
Bubble Sort
Bubble Sort compares each pair of adjacent elements and swaps them if they are in the wrong order.
This process is repeated until no swaps are needed, indicating that the list is sorted.
Page 1 of 14
How It Works
Start with the first element.
Compare it to the next element.
Swap if the first is greater.
Move to the next pair and repeat until the end.
Repeat the entire process for the list until sorted.
Algorithm
1. For each element in the list:
1. Compare the current element with the next element.
2. If the current element is greater, swap them.
2. Repeat until no swaps are needed.
Time Complexity
Worst and Average: O(n²)
Best (already sorted): O(n)
Space Complexity
O(1) (In-place sorting)
Visualization
Page 2 of 14
Insertion Sort
Insertion Sort builds the sorted array one element at a time by comparing each new element with those
already sorted and inserting it at the correct position.
How It Works
Begin with the second element.
Compare it with elements before it.
Shift elements that are greater one position ahead.
Insert the element at the correct spot.
Repeat for all elements.
Algorithm
1. Start from the second element (index 1).
2. Compare it with elements before it.
3. Shift elements larger than it to the right.
4. Insert the current element into its correct position.
5. Repeat until the array is sorted.
Time Complexity
Page 3 of 14
Worst and Average: O(n²)
Best (already sorted): O(n)
Space Complexity
O(1) (In-place sorting)
Visualization
Selection Sort
Page 4 of 14
Selection Sort repeatedly selects the smallest (or largest) element from the unsorted part and moves it
to the front.
How It Works
Find the smallest element in the unsorted portion.
Swap it with the first unsorted element.
Move the boundary of the unsorted part one step forward.
Repeat until all elements are sorted.
Algorithm
1. For each position in the array:
1. Find the minimum element in the unsorted portion.
2. Swap it with the element at the current position.
2. Continue until the entire array is sorted.
Time Complexity
Worst, Average, Best: O(n²)
Space Complexity
O(1) (In-place sorting)
Visualization
Page 5 of 14
Merge Sort
Merge Sort uses the divide-and-conquer strategy. It divides the array into halves, sorts each half, and
merges them back together.
How It Works
Divide the list into halves until each sublist has one element.
Merge adjacent sublists in sorted order.
Repeat until the entire list is merged and sorted.
Page 6 of 14
Algorithm
1. If the list has one element, it is sorted.
2. Otherwise:
1. Divide the list into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves into a single sorted list.
Time Complexity
Always O(n log n)
Space Complexity
O(n) (due to auxiliary arrays used during merging)
Visualization
Page 7 of 14
Quick Sort
Quick Sort is a highly efficient sorting algorithm that uses partitioning around a pivot element.
How It Works
Choose a pivot element.
Partition the array so elements less than the pivot come before it and those greater come after.
Recursively apply the same process to the left and right partitions.
Page 8 of 14
Algorithm
1. If the list has zero or one element, it is sorted.
2. Choose a pivot element.
3. Partition the array into:
Elements less than the pivot.
Elements greater than the pivot.
4. Recursively apply quick sort to the partitions.
Time Complexity
Worst Case: O(n²) (when pivot is poorly chosen)
Average and Best Case: O(n log n)
Space Complexity
O(log n) due to recursion stack
Visualization
Page 9 of 14
Java Implementation of Sorting Algorithms
Below is a Java class named Sorting that contains implementations of all the sorting algorithms
discussed above. Each sorting method operates on an integer array, and the main method
demonstrates calling these functions on example data.
public class Sorting {
// Bubble Sort
public static void bubbleSort(int[] arr) {
int n = [Link];
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // array already sorted
}
}
// Insertion Sort
public static void insertionSort(int[] arr) {
int n = [Link];
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1],
// that are greater than key, one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Page 10 of 14
// Selection Sort
public static void selectionSort(int[] arr) {
int n = [Link];
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Find the minimum element in unsorted part
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// Merge Sort
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge sorted halves
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
// Sizes of two subarrays
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temp arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data
[Link](arr, left, L, 0, n1);
[Link](arr, mid + 1, R, 0, n2);
Page 11 of 14
// Merge temp arrays back into arr[left..right]
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
// Copy remaining elements of L[]
while (i < n1) {
arr[k++] = L[i++];
}
// Copy remaining elements of R[]
while (j < n2) {
arr[k++] = R[j++];
}
}
// Quick Sort
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
Page 12 of 14
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// Utility method to print the array
public static void printArray(int[] arr) {
for (int value : arr) [Link](value + " ");
[Link]();
}
public static void main(String[] args) {
int[] array1 = {64, 34, 25, 12, 22, 11, 90};
int[] array2 = [Link]();
int[] array3 = [Link]();
int[] array4 = [Link]();
int[] array5 = [Link]();
[Link]("Original array:");
printArray(array1);
bubbleSort(array1);
[Link]("Bubble Sorted:");
printArray(array1);
insertionSort(array2);
[Link]("Insertion Sorted:");
printArray(array2);
selectionSort(array3);
[Link]("Selection Sorted:");
printArray(array3);
mergeSort(array4, 0, [Link] - 1);
[Link]("Merge Sorted:");
printArray(array4);
Page 13 of 14
quickSort(array5, 0, [Link] - 1);
[Link]("Quick Sorted:");
printArray(array5);
}
}
Page 14 of 14