Merge Sort

Merge Sort is a popular sorting algorithm that uses a divide-and-conquer approach to sort an array or list. Merge Sort works by recursively dividing an array or list into smaller sub-arrays until each sub-array contains only one element (which is trivially sorted). Then, it repeatedly merges these smaller sorted sub-arrays to produce a larger, sorted array. It's efficient and stable, with a time complexity of O(n log n) in the worst, average, and best cases. Here's a detailed algorithm for Merge Sort.

Algorithm:

Divide: Divide the unsorted list into two sublists of about equal size. You can do this by finding the middle point of the list.
Divide the unsorted array into two halves.Find the middle of the array by calculating 
middle = (start + end) // 2, where start is the index of the first element, and end is the index of the last element.

Conquer: Recursively sort both sublists. This is done by applying the merge sort algorithm to each sublist until they become smaller sublists or single elements (base case).
Apply the Merge Sort algorithm to the left half of the array, i.e., the portion from start to middle.
Apply the Merge Sort algorithm to the right half of the array, i.e., the portion from middle + 1 to end.

Merge: Merge the two sorted sublists back into a single sorted list. This is the "conquer" step, where you combine the sublists while maintaining the sorted order.

Merge the sorted halves to create a single sorted array.Create two pointers, one for each half (e.g., left_ptr for the left half and right_ptr for the right half).
Compare the elements at the current positions of the two pointers and select the smaller element to add to the merged array.
Move the pointer of the selected element to the next position.
Repeat the comparison and addition until you have merged all elements from both halves into a single sorted array.

Repeat steps 1 to 3 recursively for each sub-array until the entire array is sorted.

Example:

Let's use a simple example to illustrate the merge sort algorithm. Suppose we have an unsorted list
 [38, 27, 43, 3, 9, 82, 10].

Split the list into two halves: [38, 27, 43] and [3, 9, 82, 10].

Recursively sort both halves:
Left half: [27, 38, 43]
Right half: [3, 9, 10, 82]

Merge the two sorted halves:Merge [27, 38, 43] and [3, 9, 10, 82] to get [3, 9, 10, 27, 38, 43, 82].

So, the sorted list is [3, 9, 10, 27, 38, 43, 82], which is the correct result.

Pseudo Code
merge_sort(arr, left, right)
    if left < right:
        mid = (left + right) / 2
        merge_sort(arr, left, mid)    // Recursively sort left half
        merge_sort(arr, mid + 1, right)  // Recursively sort right half
        merge(arr, left, mid, right)  // Merge the two sorted halves

merge(arr, left, mid, right)
    n1 = mid - left + 1
    n2 = right - mid

    // Create temporary arrays
    left_half[n1], right_half[n2]

    // Copy data to temporary arrays left_half[] and right_half[]
    for i = 0 to n1 - 1:
        left_half[i] = arr[left + i]
    for j = 0 to n2 - 1:
        right_half[j] = arr[mid + 1 + j]

    // Merge the temporary arrays back into arr[left..right]
    i = 0
    j = 0
    k = left

    while i < n1 and j < n2:
        if left_half[i] <= right_half[j]:
            arr[k] = left_half[i]
            i++
        else:
            arr[k] = right_half[j]
            j++
        k++

    // Copy the remaining elements of left_half[], if any
    while i < n1:
        arr[k] = left_half[i]
        i++
        k++

    // Copy the remaining elements of right_half[], if any
    while j < n2:
        arr[k] = right_half[j]
        j++
        k++

Time Complexity:

Best Case: O(n log n) - Merge Sort divides the input array into two halves recursively until it reaches sub-arrays of size 1 or 0. The merging step takes O(n) time in each level of recursion, and there are log₂(n) levels of recursion, resulting in a best-case time complexity of O(n log n).

Average Case: O(n log n) - Merge Sort's average-case time complexity is the same as its best-case time complexity. It consistently divides the input in half and merges the sub-arrays, leading to O(n log n) time.

Worst Case: O(n log n) - Merge Sort's worst-case time complexity is also O(n log n). This is because, in each level of recursion, the input is divided in half, and even in the worst-case scenario, merging two sub-arrays takes O(n) time.

Space Complexity:

Merge Sort has a space complexity of O(n) due to the additional memory required to store temporary sub-arrays during the merging process. Specifically, for each level of recursion, temporary arrays of size n are created, and there are log₂(n) levels of recursion. Therefore, the space complexity is O(n) for the additional memory used during the sorting process.

In practice, this means that Merge Sort is not an in-place sorting algorithm (unlike algorithms like Quick Sort), as it requires additional memory proportional to the size of the input array. However, it is a stable and efficient sorting algorithm, making it a good choice when memory usage is not a primary concern.

C Program - Merge Sort
/*******************************************************************************/
#include <stdio.h>

// Function to merge two subarrays of arr[]
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temporary arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temporary arrays back into arr[l..r]
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Main function to perform merge sort
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for large l and r
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}

int main() {
  int arr[50],n,i;
 
  printf("Enter size of the array: ");
  scanf("%d",&n);
  printf("Enter %d elements: ",n);
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);

    mergeSort(arr, 0, n - 1);

    printf("\nSorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
        }

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Stack

Image
A stack is a fundamental data structure in computer science and programming that follows the Last-In, First-Out (LIFO) principle . It is named "stack" because it resembles a stack of items, like a stack of plates or books, where you can only add or remove items from the top. Stacks are used for various purposes in programming and are essential in many algorithms and applications. Let's delve into the details of stacks: Key Operations:  A stack typically supports two primary operations: Push: This operation adds an element to the top of the stack. It is analogous to placing an item on top of the stack. Pop: This operation removes and returns the top element of the stack. It is like taking the top item off the stack. Additionally, stacks often provide the following operations: Peek (or Top): This operation retrieves the top element without removing it. It allows you to examine the top item without modifying the stack. IsEmpty: This operation checks if the stack is empty.
Read more

Quick Sort

Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a detailed algorithm for the Quick Sort algorithm: Algorithm: Quick Sort 1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance. 2,Partition the array into two sub-arrays:     Elements less than the pivot (left sub-array).     Elements greater than the pivot (right sub-array). 3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays. 4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted ar
Read more