Home/Learn/DSA/Sorting Algorithms

Sorting Algorithms

Q: Find the kth largest element in an array

Find the kth largest element in an array - A Medium difficulty question commonly asked at Facebook. Study Sorting Algorithms patterns and Java implementation to solve this.

Q: Merge intervals — sort then merge overlapping intervals

Merge intervals — sort then merge overlapping intervals - A Medium difficulty question commonly asked at Google. Study Sorting Algorithms patterns and Java implementation to solve this.

Q: Count inversions in an array using merge sort

Count inversions in an array using merge sort - A Medium difficulty question commonly asked at Microsoft. Study Sorting Algorithms patterns and Java implementation to solve this.

Intermediate

From O(n²) basics to O(n log n) divide-and-conquer — understand the tradeoffs and when each algorithm wins.

Think of it this way

Think of organising a bookshelf by height. You could compare each pair of books and swap them one at a time — that is Bubble Sort, slow but simple. Or you could split the shelf in two halves, sort each half separately, then carefully merge them back — that is Merge Sort, much faster. Different strategies, same goal: everything in the right order.

In code, it looks like thisJava

int[] arr = {5, 2, 8, 1, 9};

// Built-in — always use this in production code
Arrays.sort(arr);                              // [1, 2, 5, 8, 9]

// Custom comparator (requires Integer[], not int[])
Integer[] arr2 = {5, 2, 8, 1, 9};
Arrays.sort(arr2, (a, b) -> b - a);           // [9, 8, 5, 2, 1] descending
Arrays.sort(arr2, Comparator.reverseOrder()); // same, more readable

Overview

Sorting is foundational to computer science. While in practice you'll use Arrays.sort(), interviews test whether you understand the algorithms underneath. Merge sort is stable and predictable at O(n log n). Quicksort is faster in practice but has O(n²) worst case. Counting sort and radix sort achieve O(n) for specific input types. Knowing these tradeoffs is what separates a strong candidate.

Time & Space Complexity

Operation	Time	Space
Bubble Sort	`O(n²)`	`O(1)`
Selection Sort	`O(n²)`	`O(1)`
Insertion Sort	`O(n²) worst, O(n) best`	`O(1)`
Merge Sort	`O(n log n)`	`O(n)`
Quick Sort	`O(n log n) avg, O(n²) worst`	`O(log n)`
Counting Sort	`O(n + k)`	`O(k)`

Java Implementation

Java

public class SortingAlgorithms {

    // Merge Sort — O(n log n), stable, O(n) space
    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);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    // Quick Sort — O(n log n) average, in-place
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    private 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 tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            }
        }
        int tmp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = tmp;
        return i + 1;
    }

    // Counting Sort — O(n + k), only for non-negative integers
    public static int[] countingSort(int[] arr, int maxVal) {
        int[] count = new int[maxVal + 1];
        for (int x : arr) count[x]++;
        int[] sorted = new int[arr.length];
        int idx = 0;
        for (int i = 0; i <= maxVal; i++) {
            while (count[i]-- > 0) sorted[idx++] = i;
        }
        return sorted;
    }
}

Key Points to Remember

Merge sort is stable and guaranteed O(n log n) — preferred when order of equal elements matters

// Stable = equal elements keep their original relative order
// Use case: sort by last name, then by first name — stability preserves outer sort

Quicksort is fastest in practice due to cache locality, but a bad pivot causes O(n²) worst case

// Avoid worst case: pick a random pivot instead of always using arr[high]
int pivotIdx = low + (int)(Math.random() * (high - low + 1));
swap(arr, pivotIdx, high); // then partition normally

Java's Arrays.sort() uses dual-pivot quicksort for primitives, TimSort (merge+insertion) for objects
Insertion sort is O(n) on nearly-sorted data — ideal when input is already mostly in order

Custom Comparator: return negative to place a before b, positive to place b before a

// Sort people by age ascending, then by name alphabetically
Arrays.sort(people, (a, b) -> a.age != b.age
    ? Integer.compare(a.age, b.age)
    : a.name.compareTo(b.name));

Interview Questions

Sort an array of 0s, 1s, and 2s without extra space (Dutch National Flag)

MediumAmazonSolve it

Find the kth largest element in an array

MediumFacebookSolve it

Merge intervals — sort then merge overlapping intervals

MediumGoogleSolve it

Count inversions in an array using merge sort

MediumMicrosoftSolve it

Sort a nearly sorted array (each element is at most k positions away)

MediumAtlassianSolve it

Ask Aria about Sorting Algorithms

Your personal AI tutor — ask anything about this concept

Graphs

Searching Algorithms