Introduction

Divide and Conquer is a powerful algorithmic paradigm that solves problems by breaking them down into smaller subproblems, solving each recursively, and combining their solutions. Two classic sorting algorithms that follow this approach are Merge Sort and Quick Sort. While they share the same strategy, they implement it differently.

Merge Sort

Merge Sort divides the array into halves recursively until each subarray has one element. Then it merges these sorted subarrays step-by-step to produce the final sorted array.

Time complexity of Merge sort

Best, Average, and Worst Case: O(n log n)

Merge Sort always divides the array into two halves and merges them in linear time. Because this behavior doesn’t depend on the input data, its time complexity remains the same regardless of the case.

Why O(n log n)?

Divide step takes log n time (number of times you can halve n).
Merge step takes O(n) time (merging two arrays of size n/2). More specifically, at each merge step, the number of arrays that need to be merged decreases by half (n/2, n/4, n/8, and so on), but the number of elements being merged at each step remains n.
So total = O(n) work per level × log n levels → O(n log n)

	Merge sort
Best case	O(log n)
Average case	O(log n)
Worst case	O(log n)

Source code of Merge sort

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 5, 2, 7, 4, 1};
        mergeSort(arr, 0, arr.length - 1);
        printArray(arr);
    }

    static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right); // O(n) merge step
        }
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }

        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }

    static void printArray(int[] arr) {
        for (int val : arr) System.out.print(val + " ");
        System.out.println();
    }
}

Quick Sort

Merge Sort divides the array into halves recursively until each subarray has one element. Then it merges these sorted subarrays step-by-step to produce the final sorted array.

Time complexity of Quick sort

Best Case: O(n log n)

The best case occurs when the pivot divides the array into two equal halves at every step. Partitioning takes O(n) and if the array is evenly split each time, the depth of recursion is log n.
Total: O(n) per level × log n levels = O(n log n)

Average Case: O(n log n)

On average, the pivot divides the array reasonably well (not necessarily in half). Over many random inputs, the average depth of the recursion tree remains around log n, and partitioning still takes O(n) at each level.

Worst Case: O(n²)

This happens when the pivot is always the smallest or largest element, leading to unbalanced partitions. One side has n – 1 elements, the other has 0.
So recursion depth = n, and at each level, partition takes O(n)

Total: O(n) + O(n – 1) + O(n – 2) + ... + O(1) = O(n²)

	Quick sort
Best case	O(log n)
Average case	O(log n)
Worst case	O(log n)

Source code of Quick sort

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 5, 2, 7, 4, 1};
        quickSort(arr, 0, arr.length - 1);
        printArray(arr);
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high); // O(n) partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    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++;
                swap(arr, i, j); // O(1) operation
            }
        }

        swap(arr, i + 1, high); // Place pivot correctly
        return i + 1;
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static void printArray(int[] arr) {
        for (int val : arr) System.out.print(val + " ");
        System.out.println();
    }
}