mergeSort<T>

A generic implementation of the Merge Sort algorithm that can sort any list of comparable elements using a divide-and-conquer approach.

Function Signature

List<T> mergeSort<T extends Comparable<T>>(List<T> list)

Parameters

• list: A list of elements of type T that implements the Comparable interface

Return Value

• Returns the sorted list of type List<T>

Type Parameters

• T extends Comparable<T>: The type parameter T must implement the Comparable interface to ensure elements can be compared

Complexity Analysis

Time Complexity

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n log n)

Space Complexity

• O(n) - Requires additional space proportional to the input size

Implementation

List<T> mergeSort<T extends Comparable<T>>(List<T> list) {
  if (list.length <= 1) return list;

  final middle = list.length ~/ 2;
  final left = list.sublist(0, middle);
  final right = list.sublist(middle);

  return _merge(mergeSort(left), mergeSort(right));
}

List<T> _merge<T extends Comparable<T>>(List<T> left, List<T> right) {
  final result = <T>[];
  var leftIndex = 0;
  var rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex].compareTo(right[rightIndex]) <= 0) {
      result.add(left[leftIndex]);
      leftIndex++;
    } else {
      result.add(right[rightIndex]);
      rightIndex++;
    }
  }

  result.addAll(left.sublist(leftIndex));
  result.addAll(right.sublist(rightIndex));

  return result;
}

Implementation Details

1. Function Declaration:

   • The function is generic, accepting any type T that implements Comparable<T>
   • Takes a single parameter list of type List<T>
   • Returns a sorted list of the same type

2. Algorithm Steps:

   • Divides the input list into two halves recursively until sublists contain one element
   • Merges the sublists by comparing elements and combining them in sorted order
   • Uses a helper function _merge to combine two sorted lists
   • Creates a new list for the merged result

Example Usage

void main() {
  // Sorting integers
  var numbers = [64, 34, 25, 12, 22, 11, 90];
  print('Original list: $numbers');
  var sortedNumbers = mergeSort(numbers);
  print('Sorted list: $sortedNumbers');

  // Sorting strings
  var fruits = ['banana', 'apple', 'orange', 'grape'];
  print('Original list: $fruits');
  var sortedFruits = mergeSort(fruits);
  print('Sorted list: $sortedFruits');
}

Output

Original list: [64, 34, 25, 12, 22, 11, 90]
Sorted list: [11, 12, 22, 25, 34, 64, 90]

Original list: [banana, apple, orange, grape]
Sorted list: [apple, banana, grape, orange]

Usage Notes

1. Type Constraints:

   • The type T must implement Comparable<T>
   • Built-in types like int, double, and String already implement Comparable
   • Custom classes must implement Comparable interface to be sorted

2. Performance Considerations:

   • Efficient for large datasets due to O(n log n) complexity
   • Requires additional memory space proportional to input size
   • Consistent performance across all input cases

3. Stability:

   • The implementation is stable - maintains relative order of equal elements
   • Useful when maintaining original order is important