Let's explore some fundamental algorithms. Suppose you're given an unsorted array of integers.

1. Describe how you would implement the following sorting algorithms:

   • Bubble Sort
   • Insertion Sort
   • Merge Sort
   • Quick Sort

2. For each algorithm, explain:

   • The basic principle behind the algorithm.
   • The time complexity in the best, average, and worst-case scenarios.
   • The space complexity.
   • Whether the algorithm is stable or unstable.

3. Provide example code snippets (in any language you prefer, but indicate which language you are using) demonstrating the core logic of each algorithm. Focus on clarity and conciseness in your code.

4. Discuss the advantages and disadvantages of each sorting algorithm. When would you choose one algorithm over another, and why? For example, consider a scenario where you have a nearly sorted array. Which algorithm would perform best, and why?

5. Imagine you're working with a very large dataset that doesn't fit into memory. Which sorting algorithm(s) could you adapt to handle this situation, and how would you do it? (Hint: Think about external sorting techniques).

To illustrate, consider an array [5, 1, 4, 2, 8]. Show how each of the listed algorithms would sort this array step by step.

Algorithms

Let's explore some fundamental algorithms. Suppose you're given an unsorted array of integers.

1. Sorting Algorithm Implementations

Here, I'll describe how to implement Bubble Sort, Insertion Sort, Merge Sort, and Quick Sort.

Bubble Sort

• Basic Principle: Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
• Time Complexity:
  • Best: O(n)
  • Average: O(n^2)
  • Worst: O(n^2)
• Space Complexity: O(1)
• Stable: Yes

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Example:

Given [5, 1, 4, 2, 8]

1. [1, 5, 4, 2, 8]
2. [1, 4, 5, 2, 8]
3. [1, 4, 2, 5, 8]
4. [1, 4, 2, 5, 8]

And so on, until [1, 2, 4, 5, 8]

Insertion Sort

• Basic Principle: Builds the final sorted array one item at a time. It assumes that the first element is sorted, then it takes the next element and inserts it in the right place among the sorted elements.
• Time Complexity:
  • Best: O(n)
  • Average: O(n^2)
  • Worst: O(n^2)
• Space Complexity: O(1)
• Stable: Yes

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j + 1] = arr[j]
                j -= 1
        arr[j + 1] = key
    return arr

Example:

Given [5, 1, 4, 2, 8]

1. [5, 1, 4, 2, 8] becomes [1, 5, 4, 2, 8]
2. [1, 5, 4, 2, 8] becomes [1, 4, 5, 2, 8]
3. [1, 4, 5, 2, 8] becomes [1, 2, 4, 5, 8]
4. [1, 2, 4, 5, 8] becomes [1, 2, 4, 5, 8]

Merge Sort

• Basic Principle: A divide and conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
• Time Complexity:
  • Best: O(n log n)
  • Average: O(n log n)
  • Worst: O(n log n)
• Space Complexity: O(n)
• Stable: Yes

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

Example:

Given [5, 1, 4, 2, 8]

1. Divide: [5, 1, 4] and [2, 8]
2. Divide: [5], [1, 4] and [2], [8]
3. Divide: [1], [4]
4. Merge: [5], [1, 4] becomes [1, 4, 5]
5. Merge: [2], [8] becomes [2, 8]
6. Merge: [1, 4, 5], [2, 8] becomes [1, 2, 4, 5, 8]

Quick Sort

• Basic Principle: A divide and conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. Always pick first element as pivot. Always pick last element as pivot (implemented below). Pick a random element as pivot. Pick median as pivot.
• Time Complexity:
  • Best: O(n log n)
  • Average: O(n log n)
  • Worst: O(n^2)
• Space Complexity: O(log n)
• Stable: No

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) - 1]
    left = []
    right = []
    equal = []
    for element in arr:
        if element < pivot:
            left.append(element)
        elif element > pivot:
            right.append(element)
        else:
            equal.append(element)
    return quick_sort(left) + equal + quick_sort(right)

Example:

Given [5, 1, 4, 2, 8]

1. Pivot is 8. Left: [5, 1, 4, 2], Right: [], Equal: [8]
2. Pivot is 2. Left: [1], Right: [5, 4], Equal: [2]
3. Pivot is 4. Left: [], Right: [5], Equal: [4]
4. Result: [1, 2, 4, 5, 8]

2. Advantages and Disadvantages

• Bubble Sort:
  • Advantage: Simple to implement.
  • Disadvantage: Very inefficient for large datasets.
• Insertion Sort:
  • Advantage: Efficient for small datasets or nearly sorted data.
  • Disadvantage: Inefficient for large datasets.
• Merge Sort:
  • Advantage: Guaranteed O(n log n) time complexity.
  • Disadvantage: Requires additional space.
• Quick Sort:
  • Advantage: Generally fast in practice.
  • Disadvantage: Worst-case O(n^2) time complexity.

When to choose:

• For nearly sorted data, Insertion Sort performs best because it has a time complexity of O(n) in the best case.
• For large datasets where guaranteed performance is needed, Merge Sort is preferred.
• For general-purpose sorting, Quick Sort is often the fastest choice.

3. Handling Large Datasets

For datasets that don't fit into memory, External Sorting techniques are used. One common approach is to use Merge Sort.

1. Divide the data into chunks that can fit into memory.
2. Sort each chunk using an in-memory sorting algorithm.
3. Merge the sorted chunks together using a k-way merge algorithm.