Algorithm Merge Sort And Quick Sort Complete Guide

Complete Examples, Step by Step for Beginners: Merge Sort and Quick Sort

Introduction

1. Merge Sort

Merge Sort is a divide-and-conquer algorithm that splits the array into halves, sorts each half, and then merges the sorted halves back into a single array.

Step-by-Step Example:

1. Divide:

   • If the array has more than one element, divide the unsorted array into two approximately equal sub-arrays.

2. Conquer:

   • Recursively sort both sub-arrays.

3. Combine:

   • Merge the two sorted sub-arrays back into a single sorted array.

Example Code in Python:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Finding the mid of the array
        left_half = arr[:mid]  # Dividing the array elements into 2 halves
        right_half = arr[mid:]

        merge_sort(left_half)  # Sorting the first half
        merge_sort(right_half)  # Sorting the second half

        i = j = k = 0

        # Copy data to temp arrays left_half[] and right_half[]
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

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

    return arr

# Testing the merge_sort function
array_to_be_sorted = [38, 27, 43, 3, 9, 82, 10]
sorted_array = merge_sort(array_to_be_sorted)
print("Sorted array:", sorted_array)

Step-by-Step Explanation:

1. Initial Call: merge_sort([38, 27, 43, 3, 9, 82, 10])
2. Divide: The array is divided into two halves: [38, 27, 43, 3] and [9, 82, 10]
3. Recursive Sorting of Left Half:
   • merge_sort([38, 27, 43, 3]) divides to [38, 27] and [43, 3]
   • merge_sort([38, 27]) divides to [38] and [27]
   • Both [38] and [27] are single elements, so they are already sorted.
   • Merge [38] and [27] to form [27, 38]
   • merge_sort([43, 3]) divides to [43] and [3]
   • Both [43] and [3] are single elements, so they are already sorted.
   • Merge [43] and [3] to form [3, 43]
   • Merge [27, 38] and [3, 43] to form [3, 27, 38, 43]
4. Recursive Sorting of Right Half:
   • merge_sort([9, 82, 10]) divides to [9] and [82, 10]
   • [9] is a single element, so it is already sorted.
   • merge_sort([82, 10]) divides to [82] and [10]
   • Both [82] and [10] are single elements, so they are already sorted.
   • Merge [82] and [10] to form [10, 82]
   • Merge [9] and [10, 82] to form [9, 10, 82]
5. Final Merge:
   • Merge [3, 27, 38, 43] and [9, 10, 82] to form [3, 9, 10, 27, 38, 43, 82]

2. Quick Sort

Quick Sort is another divide-and-conquer algorithm. It picks an element as a pivot and partitions the array around the pivot. The sub-arrays are then recursively sorted.

Step-by-Step Example:

1. Choose a Pivot:

   • Select a pivot element from the array.

2. Partition:

   • Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.

3. Recursive Sort:

   • Recursively apply the above steps to the sub-arrays of elements with smaller and larger values.

Example Code in Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]  # Choosing the middle element as the pivot
        left = [x for x in arr if x < pivot]  # Elements less than the pivot
        middle = [x for x in arr if x == pivot]  # Elements equal to the pivot
        right = [x for x in arr if x > pivot]  # Elements greater than the pivot
        return quick_sort(left) + middle + quick_sort(right)

# Testing the quick_sort function
array_to_be_sorted = [38, 27, 43, 3, 9, 82, 10]
sorted_array = quick_sort(array_to_be_sorted)
print("Sorted array:", sorted_array)

Step-by-Step Explanation:

1. Initial Call: quick_sort([38, 27, 43, 3, 9, 82, 10])
2. Choose a Pivot: Pivot = 43 (middle element of the array)
3. Partition:
   • Elements less than 43: [38, 27, 3, 9, 10]
   • Elements equal to 43: [43]
   • Elements greater than 43: [82]
4. Recursive Sorting:
   • quick_sort([38, 27, 3, 9, 10]):
     • Pivot = 3 (middle element)
     • Elements less than 3: []
     • Elements equal to 3: [3]
     • Elements greater than 3: [38, 27, 9, 10]
     • quick_sort([]) returns []
     • quick_sort([38, 27, 9, 10]):
       • Pivot = 9 (middle element)
       • Elements less than 9: [27, 10]
       • Elements equal to 9: [9]
       • Elements greater than 9: [38]
       • quick_sort([27, 10]):
         • Pivot = 10 (middle element)
         • Elements less than 10: [10]
         • Elements equal to 10: [10]
         • Elements greater than 10: []
         • quick_sort([10]) returns [10]
         • quick_sort([]) returns []
         • Merge: [10] + [10] + [] => [10, 10]
         • Merge: [27] + [10, 10] + [38] => [10, 10, 27, 38]
       • Merge: [10, 10, 27, 38] + [9] + [38] => [9, 10, 10, 27, 38]
     • Merge: [] + [3] + [9, 10, 10, 27, 38] => [3, 9, 10, 10, 27, 38]
   • quick_sort([82]) returns [82]
5. Final Merge:
   • Merge: [3, 9, 10, 27, 38] + [43] + [82] => [3, 9, 10, 27, 38, 43, 82]

Summary

• Merge Sort: It is a stable and predictable algorithm with a time complexity of (O(n \log n)). It requires additional space.
• Quick Sort: It is generally faster on average with a time complexity of (O(n \log n)), but its worst-case time complexity is (O(n^2)). It is an in-place sort.