Search

Merge Sort

Merge Sort is a stable comparison sort algorithm with exceptional performance. Merge Sort uses the merging method and performs at O(n log (n)) in the best, average, and worst case.

Table of contents

Performance

Best
Ω(n log(n))
Average
Θ(n log(n))
Worst
O(n log(n))

Code

class MergeSort {
    public static void main(String[] args)
    {
        int[]     array  = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
        MergeSort sorter = new MergeSort();
        sorter.mergeSort(array, 0, array.length - 1);
        System.out.println(java.util.Arrays.toString(array));
    }

    // main function that sorts array[start..end] using merge()
    void mergeSort(int[] array, int start, int end)
    {
        // base case
        if (start < end)
        {
            // find the middle point
            int middle = (start + end) / 2;

            mergeSort(array, start, middle); // sort first half
            mergeSort(array, middle + 1, end);  // sort second half

            // merge the sorted halves
            merge(array, start, middle, end);
        }
    }

    // merges two subarrays of array[].
    void merge(int[] array, int start, int middle, int end)
    {
        int[] leftArray  = new int[middle - start + 1];
        int[] rightArray = new int[end - middle];

        // fill in left array
        for (int i = 0; i < leftArray.length; ++i)
            leftArray[i] = array[start + i];

        // fill in right array
        for (int i = 0; i < rightArray.length; ++i)
            rightArray[i] = array[middle + 1 + i];

        /* Merge the temp arrays */

        // initial indexes of first and second subarrays
        int leftIndex = 0, rightIndex = 0;

        // the index we will start at when adding the subarrays back into the main array
        int currentIndex = start;

        // compare each index of the subarrays adding the lowest value to the currentIndex
        while (leftIndex < leftArray.length && rightIndex < rightArray.length)
        {
            if (leftArray[leftIndex] <= rightArray[rightIndex])
            {
                array[currentIndex] = leftArray[leftIndex];
                leftIndex++;
            }
            else
            {
                array[currentIndex] = rightArray[rightIndex];
                rightIndex++;
            }
            currentIndex++;
        }

        // copy remaining elements of leftArray[] if any
        while (leftIndex < leftArray.length) array[currentIndex++] = leftArray[leftIndex++];

        // copy remaining elements of rightArray[] if any
        while (rightIndex < rightArray.length) array[currentIndex++] = rightArray[rightIndex++];
    }
}
class MergeSortGeneric<T extends Comparable<? super T>> {
    public static void main(String[] args)
    {
        // example using Strings
        String[]                 arrayOfStrings = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", "Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
        MergeSortGeneric<String> stringSorter   = new MergeSortGeneric<>();
        stringSorter.mergeSort(arrayOfStrings, 0, arrayOfStrings.length - 1);
        System.out.println(java.util.Arrays.toString(arrayOfStrings));

        // example using Doubles
        Double[]                 arrayOfDoubles = {0.35, 0.02, 0.36, 0.82, 0.27, 0.49, 0.41, 0.17, 0.30, 0.89, 0.37, 0.66, 0.82, 0.17, 0.20, 0.96, 0.18, 0.25, 0.37, 0.52};
        MergeSortGeneric<Double> doubleSorter   = new MergeSortGeneric<>();
        doubleSorter.mergeSort(arrayOfDoubles, 0, arrayOfDoubles.length - 1);
        System.out.println(java.util.Arrays.toString(arrayOfDoubles));
    }

    // main function that sorts array[start..end] using merge()
    void mergeSort(T[] array, int start, int end)
    {
        // base case
        if (start < end)
        {
            // find the middle point
            int middle = (start + end) / 2;

            mergeSort(array, start, middle); // sort first half
            mergeSort(array, middle + 1, end);  // sort second half

            // merge the sorted halves
            merge(array, start, middle, end);
        }
    }

    // merges two subarrays of array[].
    void merge(T[] array, int start, int middle, int end)
    {
        T[] leftArray  = (T[]) new Comparable[middle - start + 1];
        T[] rightArray = (T[]) new Comparable[end - middle];

        // fill in left array
        for (int i = 0; i < leftArray.length; ++i)
            leftArray[i] = array[start + i];

        // fill in right array
        for (int i = 0; i < rightArray.length; ++i)
            rightArray[i] = array[middle + 1 + i];

        /* Merge the temp arrays */

        // initial indexes of first and second subarrays
        int leftIndex = 0, rightIndex = 0;

        // the index we will start at when adding the subarrays back into the main array
        int currentIndex = start;

        // compare each index of the subarrays adding the lowest value to the currentIndex
        while (leftIndex < leftArray.length && rightIndex < rightArray.length)
        {
            if (leftArray[leftIndex].compareTo(rightArray[rightIndex]) <= 0)
            {
                array[currentIndex] = leftArray[leftIndex];
                leftIndex++;
            }
            else
            {
                array[currentIndex] = rightArray[rightIndex];
                rightIndex++;
            }
            currentIndex++;
        }

        // copy remaining elements of leftArray[] if any
        while (leftIndex < leftArray.length) array[currentIndex++] = leftArray[leftIndex++];

        // copy remaining elements of rightArray[] if any
        while (rightIndex < rightArray.length) array[currentIndex++] = rightArray[rightIndex++];
    }
}
#include <iostream>
#include <vector>

// merges two subarrays of array[].
void merge(std::vector<int> &arr, int start, int middle, int end) {

    std::vector<int> leftArray(middle - start + 1);
    std::vector<int> rightArray(end - middle);

    // fill in left array
    for (int i = 0; i < leftArray.size(); ++i)
        leftArray[i] = arr[start + i];

    // fill in right array
    for (int i = 0; i < rightArray.size(); ++i)
        rightArray[i] = arr[middle + 1 + i];

    /* Merge the temp arrays */

    // initial indexes of first and second subarrays
    int leftIndex = 0, rightIndex = 0;

    // the index we will start at when adding the subarrays back into the main array
    int currentIndex = start;

    // compare each index of the subarrays adding the lowest value to the currentIndex
    while (leftIndex < leftArray.size() && rightIndex < rightArray.size()) {
        if (leftArray[leftIndex] <= rightArray[rightIndex]) {
            arr[currentIndex] = leftArray[leftIndex];
            leftIndex++;
        } else {
            arr[currentIndex] = rightArray[rightIndex];
            rightIndex++;
        }
        currentIndex++;
    }

    // copy remaining elements of leftArray[] if any
    while (leftIndex < leftArray.size()) arr[currentIndex++] = leftArray[leftIndex++];

    // copy remaining elements of rightArray[] if any
    while (rightIndex < rightArray.size()) arr[currentIndex++] = rightArray[rightIndex++];
}

// main function that sorts array[start..end] using merge()
void mergeSort(std::vector<int> &arr, int start, int end) {
    // base case
    if (start < end) {
        // find the middle point
        int middle = (start + end) / 2;

        mergeSort(arr, start, middle); // sort first half
        mergeSort(arr, middle + 1, end);  // sort second half

        // merge the sorted halves
        merge(arr, start, middle, end);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    mergeSort(arr, 0, static_cast<int>(arr.size() - 1));
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}
let array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
mergeSort(array, 0, array.length - 1)
alert(array)

// main function that sorts array[start..end] using merge()
function mergeSort(array, start, end) {
  // base case
  if (start < end) {
    // find the middle point
    let middle = Math.floor((start + end) / 2)

    mergeSort(array, start, middle) // sort first half
    mergeSort(array, middle + 1, end)  // sort second half

    // merge the sorted halves
    merge(array, start, middle, end)
  }
}

// merges two subarrays of array[]
function merge(array, start, middle, end) {
  // create temp arrays
  let leftArrayLength = middle - start + 1
  let rightArrayLength = end - middle

  let leftArray = []
  let rightArray = []

  // fill in left array
  for (let i = 0; i < leftArrayLength; ++i)
    leftArray[i] = array[start + i]

  // fill in right array
  for (let i = 0; i < rightArrayLength; ++i)
    rightArray[i] = array[middle + 1 + i]

  // merge the temp arrays

  // initial indexes of first and second subarrays
  let leftIndex = 0, rightIndex = 0

  // the index we will start at when adding the subarrays back into the main array
  let currentIndex = start;

  // compare each index of the subarrays adding the lowest value to the currentIndex
  while (leftIndex < leftArrayLength && rightIndex < rightArrayLength) {
    if (leftArray[leftIndex] <= rightArray[rightIndex])
      array[currentIndex] = leftArray[leftIndex++]
    else
      array[currentIndex] = rightArray[rightIndex++]
    currentIndex++
  }

  // copy remaining elements of leftArray[] if any
  while (leftIndex < leftArrayLength) array[currentIndex++] = leftArray[leftIndex++]

  // copy remaining elements of rightArray[] if any
  while (rightIndex < rightArrayLength) array[currentIndex++] = rightArray[rightIndex++]
}
def merge_sort(array):
    if len(array) > 1:
        middle = len(array) // 2  # divide array length in half and use the "//" operator to *floor* the result

        left_array = array[:middle]  # fill in left array
        right_array = array[middle:]  # fill in right array

        merge_sort(left_array)  # Sorting the first half
        merge_sort(right_array)  # Sorting the second half

        left_index = 0
        right_index = 0
        current_index = 0

        # compare each index of the subarrays adding the lowest value to the current_index
        while left_index < len(left_array) and right_index < len(right_array):
            if left_array[left_index] < right_array[right_index]:
                array[current_index] = left_array[left_index]
                left_index += 1
            else:
                array[current_index] = right_array[right_index]
                right_index += 1
            current_index += 1

        # copy remaining elements of left_array[] if any
        while left_index < len(left_array):
            array[current_index] = left_array[left_index]
            left_index += 1
            current_index += 1

        # copy remaining elements of right_array[] if any
        while right_index < len(right_array):
            array[current_index] = right_array[right_index]
            right_index += 1
            current_index += 1

if __name__ == '__main__':
    array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
    merge_sort(array)
    print(array)

Walkthrough

The algorithm executes in the following steps:

  1. Initialize the main mergeSort() function passing in the array, the first index, and the last index.
  2. Find the index in the middle of the first and last index passed into the mergeSort() function. Save this to a variable called middle.
  3. Make 2 recursive calls to the mergeSort() function:
    1. The first includes indexes from 0...middle
    2. The second includes indexes from middle+1...lastIndex

These recursive calls will run until there is only one item passed into each subarray. At this point, the merge() function is called to begin merging the smaller subarrays into a larger sorted array.

merge()

  1. The merge() function typically gets 4 parameters: the complete array and the starting, middle, and ending index of the subarray. The start, middle, and end index are used to create 2 subarrays, the first ranging from start to middle and second ranging from middle to end. At this point, each subarray is in the correct order.
  2. The two subarrays are merged back together in order.

Discussion