insertionSort<T>

A generic implementation of the Insertion Sort algorithm that can sort any list of comparable elements.

Function Signature

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

Parameters

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

Return Value

• Returns a new 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) - When the list is already sorted
• Average Case: O(n²)
• Worst Case: O(n²) - When the list is sorted in reverse order

Space Complexity

• O(1) - Only requires a single additional memory space for the key

Implementation

Here's a generic implementation of the Insertion Sort algorithm in Dart:

List<T> insertionSort<T extends Comparable<T>>(List<T> list) {
  final result = List<T>.from(list);

  for (var i = 1; i < result.length; i++) {
    var key = result[i];
    var j = i - 1;

    while (j >= 0 && result[j].compareTo(key) > 0) {
      result[j + 1] = result[j];
      j--;
    }
    result[j + 1] = key;
  }

  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:

   • Creates a copy of the input list to maintain immutability
   • For each element starting from index 1:
     • Stores the current element as the key
     • Compares it with previous elements
     • Shifts greater elements one position ahead
     • Places the key in its correct position

Example Usage

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

  // Sorting strings
  var fruits = ['banana', 'apple', 'orange', 'grape'];
  print('Original list: $fruits');
  var sortedFruits = insertionSort(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:

   • Best suited for small lists (< 1000 elements)
   • Not recommended for large datasets due to O(n²) complexity
   • More efficient in practice than most other quadratic algorithms
   • Adaptive: efficiency increases the more nearly sorted the data is

3. Stability:

   • Stable sorting algorithm: maintains relative order of equal elements
   • In-place algorithm: requires only O(1) additional memory space
   • Preserves the relative positioning of records with equal keys