Insertion Sort:
Insertion Sort is a simple, comparison-based, in-place sorting algorithm that builds
the final sorted array (or list) one element at a time. It works by taking one element
from the unsorted portion of the array and inserting it into its correct position in the
already sorted portion, shifting elements as necessary to make space.
Rules of Insertion Sort:
1. Start from the second element:
The first element is considered already sorted.
2. Select the current element (key):
Take the element from the unsorted part of the array.
3. Compare with the sorted portion:
Compare the key with elements in the sorted portion from right to left.
4. Shift elements:
If an element in the sorted portion is greater than the key, shift it one position to
the right.
5. Insert the key:
Place the key in the correct position in the sorted portion.
Example:
Array: [5, 2, 4, 6, 1, 3]
Ste
Array State Action
p
1 [5, 2, 4, 6, 1, 3] Start with key = 2
2 [2, 5, 4, 6, 1, 3] Insert 2 before 5
3 [2, 4, 5, 6, 1, 3] Insert 4 before 5
4 [2, 4, 5, 6, 1, 3] 6 is already in place
5 [1, 2, 4, 5, 6, 3] Insert 1 at start
6 [1, 2, 3, 4, 5, 6] Insert 3 in correct place
Complexity:
Time Complexity:
Best case (already sorted): O(n)O(n)O(n)
Worst case (reverse sorted): O(n2)O(n^2)O(n2)
Space Complexity: O(1)O(1)O(1) (in-place sorting)
Stable: Yes (doesn’t change the order of equal elements)
Definition of Merge Sort:
Merge Sort is a divide-and-conquer, comparison-based sorting algorithm that
divides the unsorted array into two halves, recursively sorts each half, and then
merges the two sorted halves to produce a fully sorted array.
Rules of Merge Sort:
1. Divide the array:
Split the array into two halves until each sub array contains only one element.
2. Recursively sort each half:
Apply merge sort to both the left and right halves.
3. Merge two sorted halves:
Compare elements from both halves and combine them into a single sorted array.
4. Repeat until fully sorted:
Continue merging sub arrays step by step until the entire array is sorted.
Step-by-Step Example:
Array: [38, 27, 43, 3, 9, 82, 10]
Step 1: Divide
Split the array repeatedly until each sub array has one element:
[38, 27, 43, 3, 9, 82, 10]
→ [38, 27, 43, 3] and [9, 82, 10]
→ [38, 27] [43, 3] and [9, 82] [10]
→ [38] [27] [43] [3] [9] [82] [10]
Step 2: Merge subarrays
Merge [38] and [27] → [27, 38]
Merge [43] and [3] → [3, 43]
Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
Merge [9] and [82] → [9, 82]
Merge [9, 82] and [10] → [9, 10, 82]
Merge [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]
Sorted Array
[3, 9, 10, 27, 38, 43, 82]
Time Complexity:
Merge Sort always divides the array in half and merges the halves. Its time
complexity is the same for all cases because it always performs the same operations.
· Best Case: O(nlogn)
· Average Case: O(nlogn)
· Worst Case: O(nlogn)
Space Complexity:
Auxiliary Space: O(n)
Merge sort requires extra space to store temporary arrays during merging.
In-place?: No (standard merge sort is not in-place).
Uses of all algorithms:
1. Insertion Sort
Uses:
Efficient for small arrays or lists (e.g., < 20 elements).
Useful when the array is nearly sorted.
Online sorting: Can sort a list as new elements arrive.
Easy to implement and stable, so useful when order of equal elements matters.
2. Merge Sort
Uses:
Efficient for large datasets.
Suitable for linked lists (does not require random access).
Stable sorting required (preserves relative order of equal elements).
Useful for external sorting, where data is too large to fit into memory.
3. Bubble Sort
Uses:
Simple educational purposes; teaching basic sorting concepts.
Rarely used in practice due to inefficiency.
Can be optimized for nearly sorted arrays.
4. Selection Sort
Uses:
Easy to understand and implement.
Useful when memory writes are costly, because it does fewer swaps.
Not stable in standard form.
5. Quick Sort
Uses:
Efficient for general-purpose sorting (average-case O(nlogn)
Often used in standard libraries (like C++ std::sort).
Works well in memory but not stable by default.
Not ideal for already sorted or nearly sorted arrays (worst case O(n2))
[Link] Sort
Uses:
Efficient, in-place, and guarantees O(n log n) time.
Useful when constant memory usage is important.
Not stable, but good for priority queues.
NAME: MALAIKA
SEMESTER: 5TH
DEPTT: COMPUTER SCIENCE
SUBMITTED TO: MISS FAIZA
TOPIC: SORTING
ALGORITHMS