This project implements the Insertion Sort Algorithm to sort arrays in monotonically decreasing order (largest to smallest). The implementation provides both in-place and non-destructive sorting variants, along with comprehensive test cases and detailed documentation.

Key Features

✅ Decreasing Order Sorting: Sorts arrays from largest to smallest
✅ Two Implementation Variants: In-place and non-destructive sorting
✅ Comprehensive Test Suite: Handles edge cases and various input scenarios
✅ Well-Documented Code: Clear comments and docstrings
✅ Educational Focus: Demonstrates algorithm concepts with examples

Architecture

Algorithm Flow Diagram

Input Array: [5, 2, 8, 1, 9, 3]
             ↓
    ┌─────────────────────────────────────┐
    │     Insertion Sort Process          │
    └─────────────────────────────────────┘
             ↓
    ┌─────────────────────────────────────┐
    │  Step 1: Start with element at i=1  │
    │  Current: 2, Sorted: [5]            │
    │  Insert 2 → [5, 2]                  │
    └─────────────────────────────────────┘
             ↓
    ┌─────────────────────────────────────┐
    │  Step 2: Process element at i=2     │
    │  Current: 8, Sorted: [5, 2]         │
    │  Insert 8 → [8, 5, 2]               │
    └─────────────────────────────────────┘
             ↓
    ┌─────────────────────────────────────┐
    │  Step 3: Process element at i=3     │
    │  Current: 1, Sorted: [8, 5, 2]      │
    │  Insert 1 → [8, 5, 2, 1]            │
    └─────────────────────────────────────┘
             ↓
    ┌─────────────────────────────────────┐
    │  Step 4: Process element at i=4     │
    │  Current: 9, Sorted: [8, 5, 2, 1]   │
    │  Insert 9 → [9, 8, 5, 2, 1]         │
    └─────────────────────────────────────┘
             ↓
    ┌─────────────────────────────────────┐
    │  Step 5: Process element at i=5     │
    │  Current: 3, Sorted: [9, 8, 5, 2, 1]│
    │  Insert 3 → [9, 8, 5, 3, 2, 1]      │
    └─────────────────────────────────────┘
             ↓
Output Array: [9, 8, 5, 3, 2, 1]

Core Algorithm Structure

┌─────────────────────────────────────────────────────────────┐
│                    Insertion Sort                           │
├─────────────────────────────────────────────────────────────┤
│  Function: insertion_sort_decreasing(arr)                   │
│  Input: Array of comparable elements                        │
│  Output: Array sorted in decreasing order                   │
├─────────────────────────────────────────────────────────────┤
│  Algorithm Steps:                                           │
│  1. Iterate through array starting from index 1             │
│  2. For each element, find its correct position             │
│  3. Shift larger elements to the right                      │
│  4. Insert current element in correct position              │
│  5. Repeat until all elements are processed                 │
└─────────────────────────────────────────────────────────────┘

Implementation Details

Core Functions

1. `insertion_sort_decreasing(arr)`

Purpose: Non-destructive sorting that returns a new sorted array
Parameters: arr (list) - Input array to be sorted
Returns: list - New array sorted in decreasing order
Space Complexity: O(n) - Creates a copy of the input array

2. `insertion_sort_decreasing_inplace(arr)`

Purpose: In-place sorting that modifies the original array
Parameters: arr (list) - Input array to be sorted (modified)
Returns: list - Same array sorted in decreasing order
Space Complexity: O(1) - Sorts in-place

Algorithm Logic

The key difference from standard insertion sort is the comparison condition:

# Standard insertion sort (ascending):
while j >= 0 and arr[j] > current_element:

# Our implementation (descending):
while j >= 0 and arr[j] < current_element:

This ensures that elements are arranged in decreasing order (largest to smallest).

Complexity Analysis

Aspect	Complexity	Description
Time Complexity	O(n²)	Worst case when array is sorted in ascending order
Space Complexity	O(1)	In-place version uses constant extra space
Best Case	O(n)	When array is already sorted in descending order
Average Case	O(n²)	Random order arrays

Usage Examples

Basic Usage

from insertion_sort_decreasing import insertion_sort_decreasing

# Example 1: Basic sorting
arr = [5, 2, 8, 1, 9, 3]
sorted_arr = insertion_sort_decreasing(arr)
print(sorted_arr)  # Output: [9, 8, 5, 3, 2, 1]

# Example 2: In-place sorting
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort_decreasing_inplace(arr)
print(arr)  # Output: [90, 64, 34, 25, 22, 12, 11]

Edge Cases Handled

# Empty array
empty_arr = []
result = insertion_sort_decreasing(empty_arr)
print(result)  # Output: []

# Single element
single = [42]
result = insertion_sort_decreasing(single)
print(result)  # Output: [42]

# Duplicate elements
duplicates = [3, 3, 3, 3]
result = insertion_sort_decreasing(duplicates)
print(result)  # Output: [3, 3, 3, 3]

Running the Program

Prerequisites

Python 3.6 or higher

Execution

python3 insertion_sort_decreasing.py

Expected Output

The program will run through 7 comprehensive test cases demonstrating:

Random unsorted arrays
Already sorted arrays (ascending and descending)
Edge cases (empty, single element, duplicates)
Larger arrays for performance demonstration

Test Cases

The implementation includes comprehensive test cases:

Random Array: [5, 2, 8, 1, 9, 3] → [9, 8, 5, 3, 2, 1]
Ascending Order: [1, 2, 3, 4, 5] → [5, 4, 3, 2, 1]
Descending Order: [5, 4, 3, 2, 1] → [5, 4, 3, 2, 1]
Single Element: [1] → [1]
Empty Array: [] → []
Duplicates: [3, 3, 3, 3] → [3, 3, 3, 3]
Large Array: [64, 34, 25, 12, 22, 11, 90] → [90, 64, 34, 25, 22, 12, 11]

Educational Value

This implementation serves as an excellent learning resource for:

Algorithm Understanding: Clear demonstration of insertion sort mechanics
Sorting Concepts: Shows how to modify algorithms for different sort orders
Code Quality: Demonstrates good practices in Python programming
Testing: Comprehensive test suite showing edge case handling
Documentation: Well-commented code with clear explanations

File Structure

MSCS532_Assignment1/
├── insertion_sort_decreasing.py    # Main implementation
├── test_insertion_sort.py         # Comprehensive test suite
├── run_tests.py                   # Test runner with various options
├── README.md                      # This documentation
└── LICENSE                        # Project license

Testing

Running Tests

The project includes a comprehensive test suite with multiple ways to run tests:

Quick Tests (Essential functionality)

python3 run_tests.py --quick

Full Test Suite

python3 run_tests.py

Unit Tests Only

python3 run_tests.py --unit-only

Performance Benchmarks

python3 run_tests.py --benchmark

Stress Tests

python3 run_tests.py --stress

Negative Test Cases

python3 run_tests.py --negative

Using unittest directly

python3 -m unittest test_insertion_sort -v

Test Coverage

The test suite includes 38 comprehensive test cases covering:

✅ Functional Tests

Basic sorting functionality
Already sorted arrays (ascending/descending)
Empty arrays and single elements
Duplicate elements
Negative numbers and zero values
Large numbers and edge cases

✅ Behavioral Tests

Non-destructive sorting (original array unchanged)
In-place sorting (original array modified)
Sorting stability (equal elements maintain order)

✅ Performance Tests

Small arrays (10-100 elements)
Worst-case performance (ascending order)
Best-case performance (descending order)
Random arrays with timing measurements

✅ Stress Tests

Edge cases and boundary conditions
Very large/small numbers
Mixed data types
Random large arrays

✅ Negative Test Cases

Invalid input types (None, strings, numbers, dicts, tuples, sets)
Non-comparable elements (mixed types)
Nested lists and complex data structures
Custom objects with/without comparison methods
Infinity and NaN values
Unicode strings and special characters
Boolean values and mixed numeric types
Very large arrays and deep recursion scenarios

Contributing

This is an educational project demonstrating insertion sort implementation. Feel free to:

Add more test cases
Implement additional sorting algorithms
Improve documentation
Optimize the implementation

License

See LICENSE file for details.

README.md

Insertion Sort Algorithm - Decreasing Order Implementation

Overview