Sorting Algorithms in Java
Implementation, Analysis, and Best Practices
bubble_chart filter_list vertical_align_bottom call_merge flash_on
Bubble Sort Selection Sort Insertion Sort Merge Sort Quick Sort
Introduction to Sorting Algorithms
info What are Sorting Algorithms?
code Algorithms Covered
• Methods to arrange elements in a specific order
(ascending/descending)
bubble_chart Bubble Sort filter_list Selection Sort
• Fundamental building blocks in computer science
• Vary in efficiency based on input size and characteristics vertical_align_bottom Insertion Sort call_merge Merge Sort
star Importance in Computer Science flash_on Quick Sort
• Optimize searching operations (binary search requires sorted
data)
assessment Key Evaluation Metrics
• Essential for data processing and analysis
• Real-world applications: databases, graphics, machine schedule Time Complexity: How runtime grows with input size
learning memory Space Complexity: Memory requirements during execution
balance Stability: Preserves relative order of equal elements
Bubble Sort
code Java Implementation schedule Time Complexity memory Space Complexity
public class BubbleSort {
Worst: O(n²) O(1) (in-place sorting)
public static void main(String[] args) { Average: O(n²)
int[] arr = {1,4,3,8,10,2,5}; Best: O(n)
int n = arr.length;
for(int i = 0; i < n-1; i++) { check_circle When to Use info Key Features
boolean swapped = false; • Small datasets • Stable sort
for(int j = 0; j < n-i-1; j++) {
• Nearly sorted data • Simple implementation
if(arr[j] > arr[j+1]) {
• Educational purposes • Adaptive (efficient for
int temp = arr[j+1];
arr[j+1] = arr[j]; nearly sorted)
arr[j] = temp;
swapped = true;
lightbulb Memory Tip
}
}
if(!swapped) break; "Bubbles" rise to the top - largest elements "bubble
} up" to their correct position with each pass through
the array.
for(int i: arr) {
System.out.print(i + " ");
}
}
}
timeline Algorithm Steps
1 Compare adjacent elements
2 Swap if they are in wrong order
3 Repeat until no more swaps needed
4 Optimization: Stop early if no swaps in a pass
Selection Sort
code Java Implementation schedule Time Complexity memory Space Complexity
public class SelectionSort {
Worst: O(n²) O(1) (in-place sorting)
public static void main(String[] args) { Average: O(n²)
int[] arr = {1,4,3,8,10,2,5}; Best: O(n²)
int n = arr.length;
for(int i = 0; i < n; i++) { check_circle When to Use info Key Features
int minIndex = i; • Small datasets • Not stable
for(int j = i; j < n; j++) {
• When memory writes are • Makes minimum number
if(arr[j] < arr[minIndex]) {
expensive of swaps
minIndex = j;
} • Simple implementation • Performance not affected
} needed by input
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
} lightbulb Memory Tip
"Select" the smallest element and place it in its
for(int i: arr) { correct position. Like selecting players for a team by
System.out.print(i + " "); picking the best one available each time.
}
}
}
timeline Algorithm Steps
1 Find the minimum element in unsorted part
2 Swap it with first element of unsorted part
3 Move boundary between sorted and unsorted parts
4 Repeat until entire array is sorted
Insertion Sort
code Java Implementation schedule Time Complexity memory Space Complexity
public class InsertionSort {
Worst: O(n²) O(1) (in-place sorting)
public static void main(String[] args) { Average: O(n²)
int[] arr = {9,14,15,12,6,8,13}; Best: O(n)
int n = arr.length;
for(int i = 0; i < n; i++) { check_circle When to Use info Key Features
int j = i; • Small datasets • Stable sort
while(j > 0 && arr[j-1] > arr[j]) {
• Nearly sorted data • Adaptive (efficient for
int temp = arr[j-1];
• Real-time data streams nearly sorted)
arr[j-1] = arr[j];
arr[j] = temp; • Online algorithm (can sort
j--; as it receives)
}
}
for(int i: arr) { lightbulb Memory Tip
System.out.print(i + " "); Like sorting playing cards in your hand - pick a card
} and insert it in the correct position among the already
} sorted cards.
}
timeline Algorithm Steps
1 Take one element at a time
2 Insert into correct position in sorted part
3 Shift elements as needed to make space
4 Repeat until all elements are sorted
Merge Sort
code Java Implementation schedule Time Complexity memory Space Complexity
public class MergeSort {
Worst: O(n log n) O(n) (requires additional
static void mergeSort(int[] arr, int low, int Average: O(n log n) space)
high) { Best: O(n log n)
if(low >= high) return;
int mid = (low + high) / 2;
mergeSort(arr, low, mid); check_circle When to Use info Key Features
mergeSort(arr, mid + 1, high); • Large datasets • Stable sort
merge(arr, low, mid, high);
• When stable sorting is • Predictable performance
}
needed • Not in-place (needs extra
static void merge(int[] arr, int low, int mid, • External sorting (large space)
int high) { files)
ArrayList temp = new ArrayList<>();
int left = low, right = mid + 1;
while(left <= mid && right <= high) { lightbulb Memory Tip
if(arr[left] <= arr[right]) { "Divide and Conquer" - split the problem into smaller
temp.add(arr[left]); parts, solve them, then merge the solutions. Like
left++; sorting a deck of cards by dividing into smaller piles,
} else {
sorting each, then combining.
temp.add(arr[right]);
right++;
}
}
while(left <= mid) {
temp.add(arr[left]);
left++;
}
while(right <= high) {
temp.add(arr[right]);
right++;
}
for(int i = low; i <= high; i++) {
arr[i] = temp.get(i - low);
}
}
}
timeline Algorithm Steps
1 Divide array into two halves
2 Recursively sort each half
3 Merge the two sorted halves
4 Continue until entire array is sorted
Quick Sort
code Java Implementation schedule Time Complexity memory Space Complexity
public class QuickSort {
Worst: O(n²) O(log n) (due to recursion
static void quicksort(int[] arr, int low, int Average: O(n log n) stack)
high) { Best: O(n log n)
if(low < high) {
int partIndex = Partition(arr, low,
high); check_circle When to Use info Key Features
quicksort(arr, low, partIndex-1); • Large datasets • Not stable
quicksort(arr, partIndex+1, high);
• Average case performance • In-place sorting
}
priority • Pivot selection affects
}
• Cache-efficient sorting performance
static int Partition(int[] arr, int low, int needed
high) {
int pivot = arr[low];
int i = low, j = high;
lightbulb Memory Tip
while(i < j) { "Quick" partitioning - pick a pivot and arrange
while(arr[i] <= pivot && i <= high-1) { elements around it. Like organizing books on a shelf
i++; by picking one and placing smaller books on one side
}
and larger on the other.
while(arr[j] > pivot && j >= low+1) {
j--;
}
if(i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
}
timeline Algorithm Steps
1 Choose a pivot element
2 Partition array around pivot (smaller left, larger right)
3 Recursively sort left and right partitions
4 Continue until entire array is sorted
Algorithm Comparison
Algorithm Time Complexity Space Complexity Stability When to Use
Best: O(n)
bubble_chart Bubble Sort Average: O(n²) O(1) Yes Small datasets, nearly sorted data, educational purposes
Worst: O(n²)
Best: O(n²)
filter_list Selection Sort Average: O(n²) O(1) No Small datasets, when memory writes are expensive
Worst: O(n²)
Best: O(n)
vertical_align_bottom Insertion Sort Average: O(n²) O(1) Yes Small datasets, nearly sorted data, real-time data streams
Worst: O(n²)
Best: O(n log n)
call_merge Merge Sort Average: O(n log n) O(n) Yes Large datasets, when stable sorting is needed, external sorting
Worst: O(n log n)
Best: O(n log n)
flash_on Quick Sort Average: O(n log n) O(log n) No Large datasets, when average case performance is priority
Worst: O(n²)
insights Key Differences & Trade-offs
Simple sorts (Bubble, Selection, Insertion) work well for small datasets but have O(n²) complexity. Efficient sorts (Merge, Quick) offer O(n log n)
performance for larger datasets. Merge Sort is stable and predictable but requires extra space. Quick Sort is generally faster in practice but has a
worst-case scenario. Insertion Sort excels with nearly sorted data, while Selection Sort minimizes memory writes.
Summary
insights Key Takeaways psychology Memory Tips
priority_high No single "best" algorithm — choice depends on bubble_chart Bubble Sort filter_list Selection Sort
specific requirements Elements "bubble up" to their "Select" the smallest element
correct position with each pass and place it in correct position
balance Trade-offs between time complexity, space
complexity, and implementation complexity
format_list_bulleted Simple algorithms (Bubble, Selection, Insertion) good vertical_align_bottom Insertion Sort call_merge Merge Sort
for small datasets
Like sorting playing cards in "Divide and Conquer"
your hand approach — split, solve, merge
speed Efficient algorithms (Merge, Quick) better for larger
datasets
fact_check Consider stability, memory constraints, and data
characteristics flash_on Quick Sort
"Quick" partitioning around a
pivot element
