Class Mergesort

java.lang.Object
topics.sorting.mergesort.Mergesort
All Implemented Interfaces:
SortingAlgorithm
public class Mergesort extends Object implements SortingAlgorithm

Mergesort

A classic divide-and-conquer algorithm. It works by recursively breaking down an array into two halves until each sub-array consists of a single element, and then merging those sub-arrays back together in a strictly sorted order.

Algorithm Steps

  1. Divide: Find the midpoint of the array to divide it into two halves.
  2. Conquer: Recursively call Mergesort for the left and right halves.
  3. Combine (Merge): Merge the two sorted halves into a single sorted sequence using an auxiliary array.

Complexity Analysis

  • Time Complexity: O(N log N) strictly in all cases (Best, Average, Worst).
  • Space Complexity: O(N) - Requires an auxiliary array of the same size as the input to merge elements securely.
  • Stability: Yes - Maintains the relative order of equal elements during the merge phase.
Author:
vicegd
See Also:
  • invalid reference 
    topics.sorting.SortingAlgorithm

  • Constructor Summary

    Constructors
    Constructor
    Description
    Mergesort()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    sort(int[] elements)
    Sorts the elements in-place silently.
    void
    sort(int[] elements, boolean trace)
    Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Mergesort

      public Mergesort()

  • Method Details

    • sort

      public void sort(int[] elements)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place silently.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.

    • sort

      public void sort(int[] elements, boolean trace)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.
      trace - If true, logs the internal state during execution.