Merge Sort Algorithm

def merge_sort_detailed(arr, depth=0):
    """Merge Sort with detailed steps"""
    indent = "  " * depth
    print(f"{indent}Dividing: {arr}")
    
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        print(f"{indent}Base case: {arr}")
        return arr
    
    # Divide the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    print(f"{indent}Left half: {left_half}")
    print(f"{indent}Right half: {right_half}")
    
    # Recursively sort both halves
    print(f"{indent}Sorting left half...")
    sorted_left = merge_sort_detailed(left_half, depth + 1)
    
    print(f"{indent}Sorting right half...")
    sorted_right = merge_sort_detailed(right_half, depth + 1)
    
    # Merge the sorted halves
    print(f"{indent}Merging {sorted_left} and {sorted_right}")
    merged = merge_detailed(sorted_left, sorted_right, depth)
    
    print(f"{indent}Merged result: {merged}")
    return merged

def merge_detailed(left, right, depth=0):
    """Merge two sorted arrays with detailed steps"""
    indent = "  " * depth
    result = []
    i = j = 0
    
    print(f"{indent}  Merging process:")
    
    # Compare elements from both arrays and add smaller one to result
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            print(f"{indent}    Added {left[i]} from left")
            i += 1
        else:
            result.append(right[j])
            print(f"{indent}    Added {right[j]} from right")
            j += 1
    
    # Add remaining elements from left array
    while i < len(left):
        result.append(left[i])
        print(f"{indent}    Added remaining {left[i]} from left")
        i += 1
    
    # Add remaining elements from right array
    while j < len(right):
        result.append(right[j])
        print(f"{indent}    Added remaining {right[j]} from right")
        j += 1
    
    return result

# Example usage
numbers = [38, 27, 43, 3, 9, 82, 10]
print("=== Merge Sort Step by Step ===")
sorted_numbers = merge_sort_detailed(numbers)

def merge_sort(arr):
    """
    Simple Merge Sort implementation
    Time Complexity: O(n log n) always
    Space Complexity: O(n)
    """
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr
    
    # Divide: find the middle point and divide array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # Conquer: recursively sort both halves
    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)
    
    # Combine: merge the sorted halves
    return merge(sorted_left, sorted_right)

def merge(left, right):
    """
    Merge two sorted arrays into one sorted array
    """
    result = []
    i = j = 0  # Pointers for left and right arrays
    
    # Compare elements and add smaller one to result
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= ensures stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Add remaining elements from left array (if any)
    result.extend(left[i:])
    
    # Add remaining elements from right array (if any)
    result.extend(right[j:])
    
    return result

# Test the function
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", test_array)
sorted_array = merge_sort(test_array)
print("Sorted array:", sorted_array)

def merge_sort_inplace(arr, left=0, right=None):
    """
    In-place Merge Sort implementation
    Time Complexity: O(n log n)
    Space Complexity: O(log n) for recursion stack
    """
    if right is None:
        right = len(arr) - 1
    
    if left < right:
        # Find the middle point
        mid = left + (right - left) // 2
        
        # Recursively sort first and second halves
        merge_sort_inplace(arr, left, mid)
        merge_sort_inplace(arr, mid + 1, right)
        
        # Merge the sorted halves
        merge_inplace(arr, left, mid, right)
    
    return arr

def merge_inplace(arr, left, mid, right):
    """
    Merge two sorted subarrays arr[left:mid+1] and arr[mid+1:right+1]
    """
    # Create temporary arrays for the two subarrays
    left_arr = arr[left:mid + 1]
    right_arr = arr[mid + 1:right + 1]
    
    # Initial indexes for left_arr, right_arr, and merged array
    i = j = 0
    k = left
    
    # Merge the temporary arrays back into arr[left:right+1]
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1
    
    # Copy remaining elements of left_arr (if any)
    while i < len(left_arr):
        arr[k] = left_arr[i]
        i += 1
        k += 1
    
    # Copy remaining elements of right_arr (if any)
    while j < len(right_arr):
        arr[k] = right_arr[j]
        j += 1
        k += 1

# Test the in-place version
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", test_array)
merge_sort_inplace(test_array)
print("Sorted array:", test_array)

🔹Hybrid Merge Sort (with Insertion Sort for small arrays)

def insertion_sort_range(arr, left, right):
    """Insertion sort for a range of array"""
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def hybrid_merge_sort(arr, left=0, right=None, threshold=10):
    """
    Hybrid Merge Sort that switches to Insertion Sort for small subarrays
    """
    if right is None:
        right = len(arr) - 1
    
    if left < right:
        # Use insertion sort for small subarrays
        if right - left + 1 <= threshold:
            insertion_sort_range(arr, left, right)
        else:
            mid = left + (right - left) // 2
            hybrid_merge_sort(arr, left, mid, threshold)
            hybrid_merge_sort(arr, mid + 1, right, threshold)
            merge_inplace(arr, left, mid, right)
    
    return arr

🔹Bottom-Up Merge Sort (Iterative)

def bottom_up_merge_sort(arr):
    """
    Iterative bottom-up merge sort
    Avoids recursion overhead
    """
    n = len(arr)
    
    # Start with subarrays of size 1, then 2, 4, 8, ...
    size = 1
    while size < n:
        # Pick starting point of left sub array
        left = 0
        while left < n - 1:
            # Calculate mid and right points
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)
            
            # Merge subarrays if mid is smaller than right
            if mid < right:
                merge_inplace(arr, left, mid, right)
            
            left = left + 2 * size
        
        size = size * 2
    
    return arr

🔹Natural Merge Sort (takes advantage of existing runs)

def natural_merge_sort(arr):
    """
    Natural merge sort that takes advantage of existing sorted runs
    """
    n = len(arr)
    if n <= 1:
        return arr
    
    while True:
        runs = find_runs(arr)
        if len(runs) <= 1:
            break
        
        # Merge adjacent runs
        new_runs = []
        i = 0
        while i < len(runs):
            if i + 1 < len(runs):
                # Merge runs[i] and runs[i+1]
                start1, end1 = runs[i]
                start2, end2 = runs[i + 1]
                merge_inplace(arr, start1, end1, end2)
                new_runs.append((start1, end2))
                i += 2
            else:
                new_runs.append(runs[i])
                i += 1
        
        runs = new_runs
    
    return arr

def find_runs(arr):
    """Find naturally occurring sorted runs in the array"""
    runs = []
    n = len(arr)
    i = 0
    
    while i < n:
        start = i
        
        # Find ascending run
        while i + 1 < n and arr[i] <= arr[i + 1]:
            i += 1
        
        # If no ascending run found, find descending run and reverse it
        if i == start:
            while i + 1 < n and arr[i] > arr[i + 1]:
                i += 1
            # Reverse the descending run
            arr[start:i + 1] = arr[start:i + 1][::-1]
        
        runs.append((start, i))
        i += 1
    
    return runs

🔹Parallel Merge Sort

import threading
from concurrent.futures import ThreadPoolExecutor

def parallel_merge_sort(arr, max_workers=4):
    """
    Parallel merge sort using multiple threads
    """
    if len(arr) <= 1:
        return arr
    
    def merge_sort_parallel(arr, depth=0, max_depth=2):
        if len(arr) <= 1:
            return arr
        
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
        
        # Use parallel processing for top levels only
        if depth < max_depth:
            with ThreadPoolExecutor(max_workers=2) as executor:
                left_future = executor.submit(merge_sort_parallel, left_half, depth + 1, max_depth)
                right_future = executor.submit(merge_sort_parallel, right_half, depth + 1, max_depth)
                
                sorted_left = left_future.result()
                sorted_right = right_future.result()
        else:
            # Use sequential merge sort for deeper levels
            sorted_left = merge_sort(left_half)
            sorted_right = merge_sort(right_half)
        
        return merge(sorted_left, sorted_right)
    
    return merge_sort_parallel(arr)

import time
import random
import math

def analyze_merge_sort():
    """Analyze Merge Sort performance characteristics"""
    
    def count_operations_merge_sort(arr):
        """Count comparisons and array accesses in merge sort"""
        comparisons = 0
        array_accesses = 0
        
        def merge_sort_count(arr):
            nonlocal comparisons, array_accesses
            
            if len(arr) <= 1:
                return arr
            
            mid = len(arr) // 2
            left = merge_sort_count(arr[:mid])
            right = merge_sort_count(arr[mid:])
            
            return merge_count(left, right)
        
        def merge_count(left, right):
            nonlocal comparisons, array_accesses
            result = []
            i = j = 0
            
            while i < len(left) and j < len(right):
                comparisons += 1
                array_accesses += 2  # Access left[i] and right[j]
                
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
                array_accesses += 1  # Append operation
            
            # Add remaining elements
            while i < len(left):
                result.append(left[i])
                array_accesses += 2
                i += 1
            
            while j < len(right):
                result.append(right[j])
                array_accesses += 2
                j += 1
            
            return result
        
        merge_sort_count(arr)
        return comparisons, array_accesses
    
    # Test different input sizes
    sizes = [10, 50, 100, 500, 1000]
    
    print("=== Merge Sort Performance Analysis ===")
    print(f"{'Size':>6} | {'Time (ms)':>10} | {'Comparisons':>12} | {'Theoretical':>12} | {'Ratio':>8}")
    print("-" * 70)
    
    for size in sizes:
        # Create random test data
        test_data = [random.randint(1, 1000) for _ in range(size)]
        
        # Measure time
        start_time = time.time()
        merge_sort(test_data.copy())
        end_time = time.time()
        
        # Count operations
        comparisons, _ = count_operations_merge_sort(test_data.copy())
        
        # Theoretical comparison count: approximately n * log2(n)
        theoretical = size * math.log2(size) if size > 1 else 0
        ratio = comparisons / theoretical if theoretical > 0 else 0
        
        print(f"{size:6d} | {(end_time - start_time)*1000:8.2f} | {comparisons:10d} | {theoretical:10.1f} | {ratio:6.2f}")

def compare_merge_implementations():
    """Compare different merge sort implementations"""
    
    implementations = {
        "Standard Merge Sort": merge_sort,
        "In-place Merge Sort": lambda arr: merge_sort_inplace(arr.copy()),
        "Hybrid Merge Sort": lambda arr: hybrid_merge_sort(arr.copy()),
        "Bottom-up Merge Sort": lambda arr: bottom_up_merge_sort(arr.copy()),
        "Natural Merge Sort": lambda arr: natural_merge_sort(arr.copy())
    }
    
    test_cases = {
        "Random": [random.randint(1, 1000) for _ in range(1000)],
        "Sorted": list(range(1000)),
        "Reverse Sorted": list(range(1000, 0, -1)),
        "Nearly Sorted": list(range(1000)),
        "Many Duplicates": [random.randint(1, 10) for _ in range(1000)]
    }
    
    # Make nearly sorted array
    nearly_sorted = test_cases["Nearly Sorted"]
    for _ in range(50):  # Swap 5% of elements
        i, j = random.randint(0, 999), random.randint(0, 999)
        nearly_sorted[i], nearly_sorted[j] = nearly_sorted[j], nearly_sorted[i]
    
    print("\n=== Implementation Comparison ===")
    
    for case_name, test_data in test_cases.items():
        print(f"\n{case_name} Data (1000 elements):")
        print("-" * 50)
        
        for impl_name, impl_func in implementations.items():
            try:
                start_time = time.time()
                result = impl_func(test_data.copy())
                end_time = time.time()
                
                # Verify correctness
                is_sorted = all(result[i] <= result[i+1] for i in range(len(result)-1))
                status = "✓" if is_sorted else "✗"
                
                print(f"{impl_name:20} | {(end_time - start_time)*1000:6.2f} ms | {status}")
            except Exception as e:
                print(f"{impl_name:20} | ERROR: {str(e)[:20]}...")

def memory_usage_analysis():
    """Analyze memory usage of different implementations"""
    import sys
    
    def get_size(obj):
        """Get approximate memory size of object"""
        return sys.getsizeof(obj)
    
    sizes = [100, 500, 1000]
    
    print("\n=== Memory Usage Analysis ===")
    print(f"{'Size':>6} | {'Standard':>10} | {'In-place':>10} | {'Difference':>12}")
    print("-" * 50)
    
    for size in sizes:
        test_data = [random.randint(1, 1000) for _ in range(size)]
        
        # Standard merge sort creates new arrays
        original_size = get_size(test_data)
        
        # Estimate memory usage (this is approximate)
        standard_extra = original_size  # Creates copies during merge
        inplace_extra = 0  # Modifies original array
        
        difference = standard_extra - inplace_extra
        
        print(f"{size:6d} | {standard_extra:8d}B | {inplace_extra:8d}B | {difference:10d}B")

# Run all analyses
analyze_merge_sort()
compare_merge_implementations()
memory_usage_analysis()

from datetime import datetime
import random

class Song:
    def __init__(self, title, artist, album, year, duration, genre, rating=0):
        self.title = title
        self.artist = artist
        self.album = album
        self.year = year
        self.duration = duration  # in seconds
        self.genre = genre
        self.rating = rating  # 0-5 stars
    
    def format_duration(self):
        """Convert seconds to MM:SS format"""
        minutes = self.duration // 60
        seconds = self.duration % 60
        return f"{minutes:02d}:{seconds:02d}"
    
    def __str__(self):
        return f"{self.title:25} | {self.artist:20} | {self.album:20} | {self.year} | {self.format_duration()} | {self.genre:12} | {'★' * self.rating}"
    
    def __repr__(self):
        return self.__str__()

class MusicLibraryOrganizer:
    def __init__(self):
        self.songs = []
    
    def add_song(self, song):
        """Add a song to the library"""
        self.songs.append(song)
    
    def merge_sort_by_title(self, songs=None):
        """Sort songs by title using merge sort"""
        if songs is None:
            songs = self.songs.copy()
        
        if len(songs) <= 1:
            return songs
        
        mid = len(songs) // 2
        left = self.merge_sort_by_title(songs[:mid])
        right = self.merge_sort_by_title(songs[mid:])
        
        return self._merge_by_title(left, right)
    
    def _merge_by_title(self, left, right):
        """Merge two sorted lists by title"""
        result = []
        i = j = 0
        
        while i < len(left) and j < len(right):
            if left[i].title.lower() <= right[j].title.lower():
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    
    def merge_sort_by_artist(self, songs=None):
        """Sort songs by artist using merge sort"""
        if songs is None:
            songs = self.songs.copy()
        
        if len(songs) <= 1:
            return songs
        
        mid = len(songs) // 2
        left = self.merge_sort_by_artist(songs[:mid])
        right = self.merge_sort_by_artist(songs[mid:])
        
        return self._merge_by_artist(left, right)
    
    def _merge_by_artist(self, left, right):
        """Merge two sorted lists by artist, then by album, then by title"""
        result = []
        i = j = 0
        
        while i < len(left) and j < len(right):
            # Primary sort: artist
            if left[i].artist.lower() < right[j].artist.lower():
                result.append(left[i])
                i += 1
            elif left[i].artist.lower() > right[j].artist.lower():
                result.append(right[j])
                j += 1
            else:
                # Secondary sort: album
                if left[i].album.lower() < right[j].album.lower():
                    result.append(left[i])
                    i += 1
                elif left[i].album.lower() > right[j].album.lower():
                    result.append(right[j])
                    j += 1
                else:
                    # Tertiary sort: title
                    if left[i].title.lower() <= right[j].title.lower():
                        result.append(left[i])
                        i += 1
                    else:
                        result.append(right[j])
                        j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    
    def merge_sort_by_year(self, songs=None, ascending=True):
        """Sort songs by year using merge sort"""
        if songs is None:
            songs = self.songs.copy()
        
        if len(songs) <= 1:
            return songs
        
        mid = len(songs) // 2
        left = self.merge_sort_by_year(songs[:mid], ascending)
        right = self.merge_sort_by_year(songs[mid:], ascending)
        
        return self._merge_by_year(left, right, ascending)
    
    def _merge_by_year(self, left, right, ascending):
        """Merge two sorted lists by year"""
        result = []
        i = j = 0
        
        while i < len(left) and j < len(right):
            if ascending:
                condition = left[i].year <= right[j].year
            else:
                condition = left[i].year >= right[j].year
            
            if condition:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    
    def merge_sort_by_rating(self, songs=None):
        """Sort songs by rating (highest first), then by title"""
        if songs is None:
            songs = self.songs.copy()
        
        if len(songs) <= 1:
            return songs
        
        mid = len(songs) // 2
        left = self.merge_sort_by_rating(songs[:mid])
        right = self.merge_sort_by_rating(songs[mid:])
        
        return self._merge_by_rating(left, right)
    
    def _merge_by_rating(self, left, right):
        """Merge two sorted lists by rating (descending), then by title"""
        result = []
        i = j = 0
        
        while i < len(left) and j < len(right):
            if left[i].rating > right[j].rating:
                result.append(left[i])
                i += 1
            elif left[i].rating < right[j].rating:
                result.append(right[j])
                j += 1
            else:
                # Same rating, sort by title
                if left[i].title.lower() <= right[j].title.lower():
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    
    def create_playlist(self, criteria):
        """Create a playlist based on criteria"""
        filtered_songs = []
        
        for song in self.songs:
            match = True
            
            if 'genre' in criteria and song.genre.lower() != criteria['genre'].lower():
                match = False
            if 'min_year' in criteria and song.year < criteria['min_year']:
                match = False
            if 'max_year' in criteria and song.year > criteria['max_year']:
                match = False
            if 'min_rating' in criteria and song.rating < criteria['min_rating']:
                match = False
            if 'artist' in criteria and criteria['artist'].lower() not in song.artist.lower():
                match = False
            
            if match:
                filtered_songs.append(song)
        
        return filtered_songs
    
    def display_songs(self, songs=None, title="Music Library", limit=None):
        """Display songs in a formatted table"""
        if songs is None:
            songs = self.songs
        
        if limit:
            songs = songs[:limit]
        
        print(f"\n🎵 {title}")
        print("=" * 120)
        print(f"{'Title':25} | {'Artist':20} | {'Album':20} | {'Year'} | {'Duration'} | {'Genre':12} | {'Rating'}")
        print("-" * 120)
        
        for song in songs:
            print(song)
        
        print(f"\nShowing {len(songs)} songs")

def create_sample_music_library():
    """Create sample music data"""
    songs_data = [
        ("Bohemian Rhapsody", "Queen", "A Night at the Opera", 1975, 355, "Rock", 5),
        ("Hotel California", "Eagles", "Hotel California", 1976, 391, "Rock", 5),
        ("Stairway to Heaven", "Led Zeppelin", "Led Zeppelin IV", 1971, 482, "Rock", 5),
        ("Imagine", "John Lennon", "Imagine", 1971, 183, "Pop", 4),
        ("Like a Rolling Stone", "Bob Dylan", "Highway 61 Revisited", 1965, 369, "Folk Rock", 4),
        ("Billie Jean", "Michael Jackson", "Thriller", 1982, 294, "Pop", 5),
        ("Hey Jude", "The Beatles", "Hey Jude", 1968, 431, "Pop", 4),
        ("Smells Like Teen Spirit", "Nirvana", "Nevermind", 1991, 301, "Grunge", 4),
        ("What's Going On", "Marvin Gaye", "What's Going On", 1971, 232, "Soul", 4),
        ("Respect", "Aretha Franklin", "I Never Loved a Man", 1967, 147, "Soul", 4),
        ("Good Vibrations", "The Beach Boys", "Smiley Smile", 1966, 219, "Pop", 3),
        ("Johnny B. Goode", "Chuck Berry", "Chuck Berry Is on Top", 1958, 161, "Rock and Roll", 4),
        ("Purple Haze", "Jimi Hendrix", "Are You Experienced", 1967, 171, "Rock", 4),
        ("Born to Run", "Bruce Springsteen", "Born to Run", 1975, 270, "Rock", 4),
        ("Bridge Over Troubled Water", "Simon and Garfunkel", "Bridge Over Troubled Water", 1970, 292, "Folk Rock", 3),
        ("The Sound of Silence", "Simon and Garfunkel", "Sounds of Silence", 1965, 200, "Folk Rock", 3),
        ("Yesterday", "The Beatles", "Help!", 1965, 125, "Pop", 3),
        ("Let It Be", "The Beatles", "Let It Be", 1970, 243, "Pop", 4),
        ("Come As You Are", "Nirvana", "Nevermind", 1991, 219, "Grunge", 3),
        ("Sweet Child O' Mine", "Guns N' Roses", "Appetite for Destruction", 1987, 356, "Hard Rock", 4)
    ]
    
    songs = []
    for title, artist, album, year, duration, genre, rating in songs_data:
        songs.append(Song(title, artist, album, year, duration, genre, rating))
    
    return songs

def main():
    # Create music library organizer
    library = MusicLibraryOrganizer()
    
    # Add sample songs
    sample_songs = create_sample_music_library()
    for song in sample_songs:
        library.add_song(song)
    
    # Display original library
    library.display_songs(title="Original Music Library")
    
    # Sort by title
    print("\n" + "="*120)
    print("SORTING BY TITLE")
    print("="*120)
    title_sorted = library.merge_sort_by_title()
    library.display_songs(title_sorted, "Songs Sorted by Title")
    
    # Sort by artist
    print("\n" + "="*120)
    print("SORTING BY ARTIST")
    print("="*120)
    artist_sorted = library.merge_sort_by_artist()
    library.display_songs(artist_sorted, "Songs Sorted by Artist → Album → Title")
    
    # Sort by year
    print("\n" + "="*120)
    print("SORTING BY YEAR")
    print("="*120)
    year_sorted = library.merge_sort_by_year(ascending=False)
    library.display_songs(year_sorted, "Songs Sorted by Year (Newest First)")
    
    # Sort by rating
    print("\n" + "="*120)
    print("SORTING BY RATING")
    print("="*120)
    rating_sorted = library.merge_sort_by_rating()
    library.display_songs(rating_sorted, "Songs Sorted by Rating (Highest First)")
    
    # Create playlists
    print("\n" + "="*120)
    print("CREATING PLAYLISTS")
    print("="*120)
    
    # Rock playlist
    rock_playlist = library.create_playlist({'genre': 'Rock'})
    rock_sorted = library.merge_sort_by_year(rock_playlist, ascending=False)
    library.display_songs(rock_sorted, "Rock Playlist (by Year)")
    
    # 5-star songs
    top_rated = library.create_playlist({'min_rating': 5})
    top_rated_sorted = library.merge_sort_by_title(top_rated)
    library.display_songs(top_rated_sorted, "5-Star Songs")
    
    # 1970s music
    seventies = library.create_playlist({'min_year': 1970, 'max_year': 1979})
    seventies_sorted = library.merge_sort_by_artist(seventies)
    library.display_songs(seventies_sorted, "1970s Music")
    
    # Beatles songs
    beatles = library.create_playlist({'artist': 'Beatles'})
    beatles_sorted = library.merge_sort_by_year(beatles)
    library.display_songs(beatles_sorted, "The Beatles Songs")
    
    # Statistics
    print("\n" + "="*120)
    print("LIBRARY STATISTICS")
    print("="*120)
    
    total_duration = sum(song.duration for song in library.songs)
    avg_duration = total_duration / len(library.songs)
    
    genres = {}
    years = {}
    ratings = {i: 0 for i in range(6)}
    
    for song in library.songs:
        genres[song.genre] = genres.get(song.genre, 0) + 1
        decade = (song.year // 10) * 10
        years[decade] = years.get(decade, 0) + 1
        ratings[song.rating] += 1
    
    print(f"Total songs: {len(library.songs)}")
    print(f"Total duration: {total_duration // 3600}h {(total_duration % 3600) // 60}m {total_duration % 60}s")
    print(f"Average duration: {avg_duration // 60:.0f}m {avg_duration % 60:.0f}s")
    
    print(f"\nGenres: {', '.join(f'{genre} ({count})' for genre, count in sorted(genres.items()))}")
    print(f"Decades: {', '.join(f'{decade}s ({count})' for decade, count in sorted(years.items()))}")
    print(f"Ratings: {', '.join(f'{rating}★ ({count})' for rating, count in ratings.items() if count > 0)}")

# Run the music library organizer
main()