Sorting

Selection Sort

class Solution {
    public int[] selectionSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; ++i) {
            int minIdx = i;
            
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
			
            int temp = nums[i];
            nums[i] = nums[minIdx];
            nums[minIdx] = temp;
        }
		
        return nums;
    }
}

The selection sort algorithm divides the input list into a sorted and an unsorted sublist. In each iteration, it finds the minimum element from the unsorted sublist and swaps it with the first element of that sublist, thereby growing the sorted sublist.

Time Complexity: O(n²), as it involves nested loops to find the minimum in the remaining array for each element.

Space Complexity: O(1), as it's an in-place sorting algorithm.

Bubble Sort

class Solution {
    public int[] bubbleSort(int[] nums) {
        for (int i = nums.length - 1; i >= 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
		
        return nums;
    }
}

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Passes through the list are repeated until the list is sorted. The largest unsorted element "bubbles" to its correct position in each pass.

Time Complexity: O(n²).

Space Complexity: O(1) for this in-place sort.

Insertion Sort

class Solution {
    public int[] insertionSort(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            int key = nums[i];
            int j = i - 1;
			
            while (j >= 0 && key < nums[j]) {
                nums[j + 1] = nums[j];
                --j;
            }
			
            nums[j + 1] = key;
        }
		
        return nums;
    }
}

Insertion sort builds the final sorted array one item at a time. It iterates through the input elements, and for each element, it finds the correct position in the already-sorted part of the array and inserts it there.

Time Complexity: O(n²) in the average and worst cases. It's efficient for small or nearly sorted datasets with a best-case time complexity of O(n).

Space Complexity: O(1).

Merge Sort

class Solution {
    public int[] mergeSort(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
		
        return nums;
    }
	
    private void mergeSort(int[] nums, int low, int high) {
		if (low >= high) return;
		
        int mid = (low + high) / 2;
		
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
		
        merge(nums, low, mid, high);
    }
	
    private void merge(int[] nums, int low, int mid, int high) {
        List<Integer> temp = new ArrayList<>();
        int left = low;
        int right = mid + 1;
		
        while (left <= mid && right <= high) {
            if (nums[left] <= nums[right]) {
                temp.add(nums[left]);
                ++left;
            } else {
                temp.add(nums[right]);
                ++right;
            }
        }
		
        while (left <= mid) {
            temp.add(nums[left]);
            ++left;
        }
		
        while (right <= high) {
            temp.add(nums[right]);
            ++right;
        }
		
        for (int i = low; i <= high; ++i) {
            nums[i] = temp.get(i - low);
        }
    }
}

Merge sort is a "divide and conquer" algorithm. It recursively divides the array into two halves until each subarray contains a single element. Then, it repeatedly merges the subarrays to produce new sorted subarrays until the entire array is sorted.

Time Complexity: O(n log n) in all cases (worst, average, and best).

Space Complexity: O(n) due to the temporary array used for merging.

Quick Sort

class Solution {
    public int[] quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
		
        return nums;
    }
	
    private void quickSort(int[] nums, int low, int high) {
        if (low >= high) return;
		
        int pivotIdx = partition(nums, low, high);
		
        quickSort(nums, low, pivotIdx - 1);
        quickSort(nums, pivotIdx + 1, high);
    }
	
    private int partition(int[] nums, int low, int high) {
        int randomIdx = low + new Random().nextInt(high - low + 1);
        swap(nums, low, randomIdx);
		
        int pivot = nums[low];
        int i = low;
        int j = high;
		
        while (i < j) {
            while (nums[i] <= pivot && i < high) {
                ++i;
            }
			
            while (nums[j] >= pivot && j > low) {
                --j;
            }
			
            if (i < j) {
                swap(nums, i, j);
            }
        }
		
        swap(nums, low, j);
        return j;
    }
	
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Quick sort is another "divide and conquer" algorithm. It works by selecting a 'pivot' element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This implementation uses a random pivot to improve performance and avoid worst-case scenarios.

Time Complexity: O(n log n) on average, but O(n²) in the worst case (though randomized pivoting makes this unlikely).

Space Complexity: O(log n) on average for the recursion stack depth. In the worst case, it can be O(n).