Array Sorting Logic
Solve one Java logic problem at a time, then flip for the complete explanation and program.
0/180
Known
filtered set
Solve one Java logic problem at a time, then flip for the complete explanation and program.
Java Logic Development · Chapter 12 Companion Article
Fifteen sorting problems — Bubble, Selection, Insertion, Merge, and Quick Sort, Counting Sort, binary and Dutch-flag partitioning, frequency ordering, and kth-element selection — each matched to the constraints that make it the right choice.
Sorting means arranging array elements according to a defined order. The most common orders are ascending and descending, but interview problems also require sorting by frequency, category, parity, or a limited set of values such as 0, 1, and 2.
Sorting problems are useful for learning:
Sort an integer array in ascending order using Bubble Sort.
[5, 1, 4, 2, 8][1, 2, 4, 5, 8]Compare adjacent elements and swap them whenever the left element is greater than the right element.
Bubble Sort repeatedly moves larger elements toward the end of the array. During one complete pass: compare index 0 with 1, compare index 1 with 2, continue until the unsorted portion ends, and the largest remaining element reaches its correct position. After each pass, one more element becomes permanently sorted. An optimization is to stop when a complete pass performs no swaps.
import java.util.Arrays;
public class BubbleSortExample {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 8};
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
System.out.println(Arrays.toString(arr));
}
}[1, 2, 4, 5, 8]Initial: [5, 1, 4, 2, 8]. First pass:
5 and 1 -> swap
[1, 5, 4, 2, 8]
5 and 4 -> swap
[1, 4, 5, 2, 8]
5 and 2 -> swap
[1, 4, 2, 5, 8]
5 and 8 -> no swapLargest element 8 is already at the end. After subsequent passes: [1, 2, 4, 5, 8].
O(n) with swap optimizationO(n²)O(n²)O(1)Bubble Sort is stable when elements are swapped only when the left value is strictly greater than the right value.
Do not run the inner loop until arr.length - 1 on every pass. The last i elements are already sorted.
Bubble Sort is mainly useful for demonstrating sorting fundamentals. It is usually not preferred for large datasets because of quadratic time complexity.
Sort an array by repeatedly selecting the smallest element from the unsorted portion.
[64, 25, 12, 22, 11][11, 12, 22, 25, 64]For every position, find the minimum element from that position to the end of the array.
Selection Sort divides the array logically into a sorted portion and an unsorted portion. For index i, find the index of the smallest value from i onward and swap it with arr[i]. Unlike Bubble Sort, Selection Sort normally performs at most one swap per outer iteration.
import java.util.Arrays;
public class SelectionSortExample {
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
}[11, 12, 22, 25, 64]Initial: [64, 25, 12, 22, 11]. Minimum from entire array: 11. Swap with 64: [11, 25, 12, 22, 64]. Next minimum from index 1 onward: 12. Result: [11, 12, 25, 22, 64]. Next minimum: 22. Result: [11, 12, 22, 25, 64].
O(n²)O(n²)O(n²)O(1)Selection Sort performs fewer swaps than Bubble Sort but still performs approximately n² / 2 comparisons.
Store the minimum element's index, not only its value. The index is required to perform the swap.
Selection Sort is useful when writes are relatively expensive because it generally performs fewer swaps than Bubble Sort.
Sort an array by inserting each element into its correct position in the already-sorted left portion.
[5, 2, 4, 6, 1, 3][1, 2, 3, 4, 5, 6]Treat the first element as sorted. Take the next value and shift larger elements one position to the right.
Insertion Sort works similarly to arranging playing cards in your hand. For every element: store it as key, compare it with elements before it, shift larger values right, and insert the key into the empty position.
import java.util.Arrays;
public class InsertionSortExample {
public static void main(String[] args) {
int[] arr = {5, 2, 4, 6, 1, 3};
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
System.out.println(Arrays.toString(arr));
}
}[1, 2, 3, 4, 5, 6]Start: [5, 2, 4, 6, 1, 3]. Insert 2 before 5: [2, 5, 4, 6, 1, 3]. Insert 4 between 2 and 5: [2, 4, 5, 6, 1, 3]. Insert 6: [2, 4, 5, 6, 1, 3]. Insert 1: [1, 2, 4, 5, 6, 3]. Insert 3: [1, 2, 3, 4, 5, 6].
O(n)O(n²)O(n²)O(1)Insertion Sort performs well on small or nearly sorted arrays. It is also stable when equal elements are not unnecessarily moved ahead of each other.
Do not overwrite arr[i] before storing it in the key variable.
Insertion Sort is commonly used as a supporting algorithm inside optimized sorting implementations for very small partitions.
Sort an array using the divide-and-conquer technique.
[38, 27, 43, 3, 9, 82, 10][3, 9, 10, 27, 38, 43, 82]Split the array into smaller halves until each part contains one element, then merge those parts in sorted order.
Merge Sort has two main operations: divide and merge. An array of multiple elements is split around the middle. For example, [8, 3, 5, 1] becomes:
[8, 3]
[5, 1]Then:
[8] [3]
[5] [1]Single-element arrays are already sorted. They are then merged:
[3, 8]
[1, 5]Finally: [1, 3, 5, 8].
import java.util.Arrays;
public class MergeSortExample {
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int x = 0; x < temp.length; x++) {
arr[left + x] = temp[x];
}
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}[3, 9, 10, 27, 38, 43, 82]Each recursive call sorts a smaller portion. The merge operation receives two already-sorted ranges, so the smallest available values can be selected one by one. Eventually every element is copied back in sorted order.
O(n log n)O(n log n)O(n log n)O(n)Merge Sort provides predictable O(n log n) performance regardless of initial element order.
After comparing both halves, remember to copy remaining elements from whichever half still contains values.
Know why Merge Sort requires extra memory for arrays and why it is well suited to linked lists and external sorting.
Sort an array using partitioning around a pivot.
[10, 7, 8, 9, 1, 5][1, 5, 7, 8, 9, 10]Choose a pivot. Move smaller values to one side and larger values to the other side.
Quick Sort uses a pivot to partition the array. After partitioning: values less than or equal to the pivot appear on its left, values greater than the pivot appear on its right, and the pivot reaches its final sorted position. The same process is recursively applied to the left and right partitions.
import java.util.Arrays;
public class QuickSortExample {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}[1, 5, 7, 8, 9, 10]Pivot: 5. Original: [10, 7, 8, 9, 1, 5]. Only 1 is smaller than 5. After partition: [1, 5, 8, 9, 10, 7]. The pivot 5 is now at its final position. Quick Sort recursively sorts [8, 9, 10, 7]. Final result: [1, 5, 7, 8, 9, 10].
O(n log n)O(n log n)O(n²)O(log n)O(n)Poor pivot choices can create heavily unbalanced partitions and cause quadratic performance.
Be prepared to explain pivot selection, partition logic, why the average complexity is O(n log n), and why worst-case complexity becomes O(n²).
Sort integers by counting how many times each value occurs.
[4, 2, 2, 8, 3, 3, 1][1, 2, 2, 3, 3, 4, 8]Instead of comparing values, maintain a frequency array.
If values lie within a manageable integer range, create a count array. For [4, 2, 2, 3], frequency information becomes conceptually:
2 -> 2 times
3 -> 1 time
4 -> 1 timeReconstruct the array using those frequencies.
import java.util.Arrays;
public class CountingSortExample {
public static void main(String[] args) {
int[] arr = {4, 2, 2, 8, 3, 3, 1};
int max = arr[0];
for (int value : arr) {
if (value > max) {
max = value;
}
}
int[] count = new int[max + 1];
for (int value : arr) {
count[value]++;
}
int index = 0;
for (int value = 0; value < count.length; value++) {
while (count[value] > 0) {
arr[index++] = value;
count[value]--;
}
}
System.out.println(Arrays.toString(arr));
}
}[1, 2, 2, 3, 3, 4, 8]Let n = number of elements and k = value range. Complexity:
O(n + k)O(k)The shown implementation works only with non-negative integers. For negative numbers, the minimum value can be used as an offset.
Counting Sort can outperform comparison-based sorting when the numeric range is reasonably small.
Do not use a huge counting array when values span a very large range, such as 1 to 1,000,000,000.
Sort array values from smallest to largest without using a built-in sorting method.
[9, 3, 7, 1, 5][1, 3, 5, 7, 9]A simple interview-friendly solution compares each element with every element after it. If the left value is greater, swap them.
import java.util.Arrays;
public class AscendingSort {
public static void main(String[] args) {
int[] arr = {9, 3, 7, 1, 5};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}[1, 3, 5, 7, 9]O(n²)O(1)If the interviewer only says "sort the array," ask whether built-in sorting is allowed, stability matters, extra space is allowed, input size is large, and values have a limited range. The best algorithm depends on these constraints.
Arrange the largest element first and the smallest element last.
[4, 8, 2, 9, 1][9, 8, 4, 2, 1]Swap when the left element is smaller than the right element.
import java.util.Arrays;
public class DescendingSort {
public static void main(String[] args) {
int[] arr = {4, 8, 2, 9, 1};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] < arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}[9, 8, 4, 2, 1]O(n²)O(1)Ascending and descending loops may look almost identical. The comparison condition determines the ordering. Ascending: arr[i] > arr[j]. Descending: arr[i] < arr[j].
Place even numbers first and odd numbers afterward, with each group sorted independently.
[5, 2, 8, 1, 4, 7, 6][2, 4, 6, 8, 1, 5, 7]This problem has two separate requirements: separate elements according to parity, then sort the even and odd groups. A clear implementation stores even and odd values separately, sorts each group manually, and copies them back.
import java.util.Arrays;
public class EvenOddSeparateSort {
public static void sort(int[] arr, int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 1, 4, 7, 6};
int[] even = new int[arr.length];
int[] odd = new int[arr.length];
int evenCount = 0;
int oddCount = 0;
for (int value : arr) {
if (value % 2 == 0) {
even[evenCount++] = value;
} else {
odd[oddCount++] = value;
}
}
sort(even, evenCount);
sort(odd, oddCount);
int index = 0;
for (int i = 0; i < evenCount; i++) {
arr[index++] = even[i];
}
for (int i = 0; i < oddCount; i++) {
arr[index++] = odd[i];
}
System.out.println(Arrays.toString(arr));
}
}[2, 4, 6, 8, 1, 5, 7]Parity determines the group: value % 2 == 0 means even. Each group is sorted independently before rebuilding the final array.
With the simple manual sort:
O(n²)O(n)The interviewer may ask for even ascending and odd descending, odd numbers first, preserving original order within both groups, or performing the partition in place. These variations require different strategies.
Sort an array without using Arrays.sort() or collection sorting utilities.
[12, 4, 7, 2, 10][2, 4, 7, 10, 12]Sorting without a built-in method means implementing the comparison and movement logic yourself. For a straightforward implementation: pick a current position, compare it with later positions, and swap whenever a smaller element is found.
import java.util.Arrays;
public class ManualArraySort {
public static void main(String[] args) {
int[] arr = {12, 4, 7, 2, 10};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[i]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}[2, 4, 7, 10, 12]O(n²)O(1)"Without built-in sorting" does not imply that O(n²) is required. Depending on the question, you can manually implement Merge Sort, Quick Sort, Heap Sort, or Counting Sort. Clarify expected performance if input can be large.
Sort a binary array containing only 0 and 1.
[1, 0, 1, 0, 0, 1][0, 0, 0, 1, 1, 1]The values are limited to only two possibilities, so general-purpose sorting is unnecessary.
Use two pointers: left starts from the beginning and right starts from the end. Move left while it points to 0. Move right while it points to 1. When left finds a 1 and right finds a 0, swap them.
import java.util.Arrays;
public class SortBinaryArray {
public static void main(String[] args) {
int[] arr = {1, 0, 1, 0, 0, 1};
int left = 0;
int right = arr.length - 1;
while (left < right) {
while (left < right && arr[left] == 0) {
left++;
}
while (left < right && arr[right] == 1) {
right--;
}
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
System.out.println(Arrays.toString(arr));
}
}[0, 0, 0, 1, 1, 1]O(n)O(1)General comparison sorting may require O(n log n). Because the possible values are known in advance, this problem can be solved in linear time.
The logic also works for [0, 0, 0] and [1, 1, 1] without unnecessary swaps.
Sort an array containing only 0, 1, and 2 without using a standard sorting algorithm.
[2, 0, 2, 1, 1, 0][0, 0, 1, 1, 2, 2]Maintain three regions for 0s, 1s, and 2s.
This is the Dutch National Flag problem. Use low for the next position of 0, mid for the current element, and high for the next position of 2.
Rules: if arr[mid] == 0, swap with low and increment both low and mid. If arr[mid] == 1, increment mid. If arr[mid] == 2, swap with high, decrement high, and do not increment mid yet — the element received from the high side has not been examined.
import java.util.Arrays;
public class DutchNationalFlag {
public static void main(String[] args) {
int[] arr = {2, 0, 2, 1, 1, 0};
int low = 0;
int mid = 0;
int high = arr.length - 1;
while (mid <= high) {
if (arr[mid] == 0) {
int temp = arr[low];
arr[low] = arr[mid];
arr[mid] = temp;
low++;
mid++;
} else if (arr[mid] == 1) {
mid++;
} else {
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
high--;
}
}
System.out.println(Arrays.toString(arr));
}
}[0, 0, 1, 1, 2, 2]Initial: [2, 0, 2, 1, 1, 0]. Initial pointers:
low = 0
mid = 0
high = 5arr[mid] is 2. Swap index 0 with index 5: [0, 0, 2, 1, 1, 2]. Now: high = 4. Current value at mid is 0. Move it into the low section. The process continues until mid > high. Final: [0, 0, 1, 1, 2, 2].
O(n)O(1)After swapping a 2 with arr[high], do not immediately increment mid. The new value at mid still needs classification.
This is an important partitioning problem because it sorts three categories in one traversal without additional storage.
Sort elements according to how frequently they occur. For this example: higher-frequency elements come first, and if frequencies are equal, smaller values come first.
[4, 6, 2, 4, 3, 4, 6, 2, 2]Frequencies:
2 -> 3
4 -> 3
6 -> 2
3 -> 1[2, 2, 2, 4, 4, 4, 6, 6, 3]Frequency must be calculated before ordering can be decided.
A HashMap stores each value and its frequency. The array is converted into Integer[] so a custom comparator can determine ordering. Comparator rules: higher frequency comes first; if frequencies match, smaller number comes first.
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class FrequencySort {
public static void main(String[] args) {
int[] arr = {4, 6, 2, 4, 3, 4, 6, 2, 2};
Map frequency = new HashMap<>();
for (int value : arr) {
frequency.put(value, frequency.getOrDefault(value, 0) + 1);
}
Integer[] values = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(values, (a, b) -> {
int frequencyCompare = Integer.compare(frequency.get(b), frequency.get(a));
if (frequencyCompare != 0) {
return frequencyCompare;
}
return Integer.compare(a, b);
});
System.out.println(Arrays.toString(values));
}
} [2, 2, 2, 4, 4, 4, 6, 6, 3]The frequency map separates counting from ordering. The comparator has access to both values' frequencies and can therefore define a custom sort order instead of simple numeric ordering.
For n elements:
O(n)O(n log n)O(n)The tie-breaking rule may be different. Possible requirements include preserving original order when frequencies match, larger value first when frequencies match, least frequent elements first, or outputting each distinct value only once. Always confirm the tie rule.
Find the kth largest element in an unsorted array.
Array = [3, 2, 1, 5, 6, 4]
k = 25After sorting ascending: [1, 2, 3, 4, 5, 6]. The kth largest element is at arr.length - k. For k = 2:
arr[6 - 2]
arr[4]
5import java.util.Arrays;
public class KthLargest {
public static void main(String[] args) {
int[] arr = {3, 2, 1, 5, 6, 4};
int k = 2;
if (k < 1 || k > arr.length) {
System.out.println("Invalid k");
return;
}
Arrays.sort(arr);
int result = arr[arr.length - k];
System.out.println(result);
}
}5Using sorting:
O(n log n)Consider [5, 5, 4, 3]. For k = 2, normal positional interpretation gives 5. If the interviewer asks for the second distinct largest, the answer would be 4. These are different problems.
Depending on constraints: sorting is O(n log n), a min-heap of size k is O(n log k), and Quickselect averages O(n).
For very large arrays with small k, sorting the entire array may do unnecessary work. A heap or Quickselect can be more appropriate.
Find the kth smallest value in an unsorted array.
Array = [7, 10, 4, 3, 20, 15]
k = 37Sort the array in ascending order. After sorting: [3, 4, 7, 10, 15, 20]. Because Java array indexes start from zero, the kth smallest value is arr[k - 1]. For k = 3: arr[2] = 7.
import java.util.Arrays;
public class KthSmallest {
public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
int k = 3;
if (k < 1 || k > arr.length) {
System.out.println("Invalid k");
return;
}
Arrays.sort(arr);
int result = arr[k - 1];
System.out.println(result);
}
}7Using sorting:
O(n log n)O(1)Do not use arr[k]. The kth smallest element is located at arr[k - 1] because array indexing begins at zero.
For repeated values, clarify whether duplicates count as individual positions. Example: [1, 2, 2, 4], second smallest by position is 2, second distinct smallest is also 2. But with [1, 1, 2, 4], second smallest by position is 1, while second distinct smallest is 2.
| Algorithm | Best | Average | Worst | Extra Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) optimized | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Usually No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) average recursion | Usually No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Depends on implementation |
k in Counting Sort represents the range of possible values, not the kth element.
These algorithms determine order by comparing elements. Examples: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort. General-purpose comparison sorting cannot guarantee better than O(n log n) comparison complexity for arbitrary input.
These algorithms use information about the values themselves. Example: Counting Sort. Counting Sort can achieve O(n + k), but only when the value range makes the auxiliary counting structure practical.
A sorting algorithm is stable when equal elements preserve their original relative order. Consider records:
(101, 90)
(102, 80)
(103, 90)If sorting by score while maintaining the original order of equal scores, employee 101 should remain before 103. Stability matters when objects are sorted repeatedly by different fields.
Common stable algorithms include Bubble Sort, Insertion Sort, and Merge Sort when implemented appropriately. Selection Sort and typical Quick Sort implementations are not inherently stable.
An in-place algorithm requires little extra memory beyond the input array. Examples: Bubble Sort, Selection Sort, Insertion Sort, and Quick Sort (often considered in-place apart from recursion stack usage). Merge Sort on arrays usually needs temporary storage proportional to the input size.
An adaptive algorithm benefits when the array is already or nearly sorted. Insertion Sort is a good example. For [1, 2, 3, 5, 4, 6], Insertion Sort performs only a small amount of shifting. An optimized Bubble Sort can also terminate early when no swaps occur.
Use Insertion Sort when input is small, data is nearly sorted, or simple in-place logic is useful.
Use Merge Sort when guaranteed O(n log n) performance is needed, stable sorting matters, or additional O(n) memory is acceptable.
Use Quick Sort when fast average performance is desired, in-place partitioning is useful, or worst-case behavior can be controlled through pivot strategy.
Use Counting Sort when values are integers, their range is limited, and O(n + k) performance is practical.
Use specialized partitioning when input contains only 0 and 1, or only 0, 1, and 2, where full general-purpose sorting would perform unnecessary work.
Swap when leftValue > rightValue. Result: smallest to largest.
Swap when leftValue < rightValue. Result: largest to smallest.
A standard integer swap uses a temporary variable:
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;The temporary variable prevents the first value from being lost after assignment.
Consider:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
}
}The inner operation can execute approximately n × n times. Therefore complexity is O(n²). Bubble Sort and Selection Sort have this general behavior.
Merge Sort repeatedly divides the array approximately in half. Number of division levels: log n. At every level, merging processes approximately n elements. Therefore n × log n gives O(n log n).
Suppose the array is already sorted, [1, 2, 3, 4, 5], and the last element is always selected as pivot. The partitions may repeatedly become:
n - 1 and 0
n - 2 and 0
n - 3 and 0Instead of balanced partitions, one side contains almost the entire array. The work approaches n + (n - 1) + (n - 2) + ... which is O(n²). Randomized or better pivot selection reduces the chance of repeatedly producing such poor partitions.
Sorting implementations should behave correctly with:
[]. No sorting operation is required.
[7]. Already sorted.
[4, 2, 4, 2]. Expected ascending result: [2, 2, 4, 4].
[-3, 5, -1, 0]. Expected result: [-3, -1, 0, 5]. Most comparison-based sorting algorithms handle negative values naturally.
[1, 2, 3, 4]. Optimized algorithms such as Insertion Sort or Bubble Sort can benefit from this condition.
[5, 4, 3, 2, 1]. This represents a worst-case arrangement for several simple sorting methods.
Wrong boundaries can cause ArrayIndexOutOfBoundsException, especially when accessing arr[j + 1]. Ensure j + 1 remains within the array.
Wrong:
arr[i] = arr[j];
arr[j] = arr[i];The original arr[i] has already been overwritten. Use a temporary variable.
Merge Sort and Quick Sort require termination conditions. Without them, recursion continues until stack failure.
Prefer int mid = left + (right - left) / 2; instead of int mid = (left + right) / 2; The first form avoids integer overflow when indexes are very large.
After placing the pivot at pivotIndex, recursive calls should exclude that position. Correct:
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);For ascending data: kth smallest is arr[k - 1], kth largest is arr[arr.length - k].
When a sorting problem appears in an interview, identify the constraints before choosing the implementation. Ask:
These details can completely change the best solution. For example, finding the kth largest element does not necessarily require sorting the entire array.
It performs O(n²) comparisons in average and worst cases, so its execution time grows quickly as the number of elements increases.
Insertion Sort because elements already near their correct position require very few shifts.
Merge Sort guarantees O(n log n) in best, average, and worst cases.
O(n²). This occurs when partitioning repeatedly produces highly unbalanced partitions.
Its average O(n log n) performance, partitioning technique, and low additional array storage make it important for understanding efficient sorting.
Yes, but the implementation must map negative values to valid array indexes, usually by offsetting values using the minimum element.
No. If the numeric range is extremely large compared with the number of elements, the count array can consume excessive memory and processing time.
During merging, when two values are equal, taking the element from the left half first preserves their previous relative order.
Swapping the selected minimum with the current position can change the relative positions of equal elements.
It is a three-way partitioning technique that divides values into three regions. A common interview application sorts arrays containing only 0, 1, and 2 in O(n) time and O(1) extra space.
No. Possible alternatives include a min-heap, a max-heap, or Quickselect. The best choice depends on n, k, memory limits, and whether the original data may be modified.
Sorting establishes complete order. Partitioning only divides values into groups according to a condition. For example, [7, 2, 5, 4] partitioning by parity could produce [2, 4, 7, 5]. The even and odd groups exist, but elements inside each group are not necessarily sorted.
After completing Array Sorting Logic, you should be able to:
Arrays.sort()O(n)O(n²), O(n log n), and O(n + k) algorithms