Skip to main content

5. Simple Sorting Algorithms

newNode->next = *head; *head = newNode; return; }

// Find position to insert
struct Node *current = *head;
while (current->next != NULL && current->next->data < newNode->data) {
    current = current->next;
}

newNode->next = current->next;
current->next = newNode;

}

void insertionSortList(struct Node **head) { struct Node *sorted = NULL; struct Node *current = *head;

while (current != NULL) {
    struct Node *next = current->next;
    sortedInsert(&sorted, current);
    current = next;
}

*head = sorted;

}


#### Complexity Analysis

**Time Complexity:**
- Best Case: O(n) - already sorted
- Average Case: O(n²)
- Worst Case: O(n²) - reverse sorted

**Space Complexity:** O(1) - in-place sorting

**Detailed Analysis:**

Best Case (sorted): [1, 2, 3, 4, 5]

  • Comparisons: n-1 (each element compared once)
  • Shifts: 0
  • Time: O(n)

Worst Case (reverse sorted): [5, 4, 3, 2, 1]

  • Comparisons: 1+2+3+...+(n-1) = n(n-1)/2
  • Shifts: Same as comparisons
  • Time: O(n²)

Average Case (random):

  • Comparisons: ~n²/4
  • Shifts: ~n²/4
  • Time: O(n²)

**Performance on Different Inputs:**
```c
void testInsertionSort() {
    // Already sorted
    int sorted[] = {1, 2, 3, 4, 5};
    printf("Sorted array: Fast! O(n)\n");
    
    // Reverse sorted
    int reverse[] = {5, 4, 3, 2, 1};
    printf("Reverse array: Slow! O(n²)\n");
    
    // Nearly sorted
    int nearlySorted[] = {1, 2, 4, 3, 5};
    printf("Nearly sorted: Fast! O(n)\n");
    
    // Few elements out of place
    int fewMoves[] = {2, 1, 3, 4, 5};
    printf("Few out of place: Fast!\n");
}

Advantages

  1. Simple implementation
  2. Stable - preserves relative order
  3. In-place - O(1) extra space
  4. Adaptive - O(n) for nearly sorted data
  5. Online - can sort as data arrives

Stability Example:

Input:  [4a, 3, 4b, 2]
Output: [2, 3, 4a, 4b]  ← Order preserved!

When to Use

Use Insertion Sort when:

  • Small datasets (n < 50)
  • Nearly sorted data
  • Stability required
  • Online sorting (data arriving in real-time)
  • Linked lists (no shifting overhead)

Don't use when:

  • Large datasets
  • Random data
  • Performance critical

Real-World Applications:

  1. Sorting small files
  2. Hybrid sorting (used in TimSort)
  3. Online algorithms
  4. Sorting linked lists
Back to top