Merge sorting in Data structure with Python Language program .

 
MERGE SORT :

MERGE Sort IS a popular AND efficient sorting algorithm that follows 
the divide-and-conquer approach TO sort an array OR list OF elements. 
It divides the INPUT INTO smaller parts, sorts them individually, AND
THEN merges the sorted parts TO obtain the final sorted RESULT.
The TIME complexity OF MERGE Sort IS O(n log n), making it one OF 
the fastest sorting algorithms FOR LARGE datasets.
 
Here's a high-level description of the Merge Sort algorithm:
 
1. *Divide*: The unsorted array is divided into two halves.
  This step continues recursively until the sub-arrays contain only
  one element, which is inherently sorted.
 
2. **Conquer (Sort)**: Each sub-array is sorted individually either by
    applying Merge Sort again on them or using a different sorting algorithm,
  like Insertion Sort or Bubble Sort, for small  enough sub-arrays.
 
3. **Combine (Merge)**: The sorted sub-arrays are merged together to create
  larger sorted arrays. This merging process combines the elements from both
  sub-arrays in a way that maintains the sorted order.
 
```Algorithm Of Merge Sort.
 
MergeSort(arr, left, right):
    if left < right:
        middle = (left + right) / 2
        MergeSort(arr, left, middle)
        MergeSort(arr, middle + 1, right)
        Merge(arr, left, middle, right)
 
Merge(arr, left, middle, right):
    n1 = middle - left + 1
    n2 = right - middle
    leftArr[n1], rightArr[n2]
 
    for i = 0 to n1 - 1:
        leftArr[i] = arr[left + i]
    for j = 0 to n2 - 1:
        rightArr[j] = arr[middle + 1 + j]
 
    i = 0, j = 0, k = left
    while i < n1 and j < n2:
        if leftArr[i] <= rightArr[j]:
            arr[k] = leftArr[i]
            i++
        else:
            arr[k] = rightArr[j]
            j++
        k++
 
    while i < n1:
        arr[k] = leftArr[i]
        i++
        k++
    while j < n2:
        arr[k] = rightArr[j]
        j++
        k++
 
 
 Keep in mind that Merge Sort is generally considered a stable sorting algorithm
 (maintains the relative order of equal elements) and is suitable for large datasets
 due to its efficient time complexity.
 
 Sure! Let's walk through an example OF MERGE Sort step BY step TO understand how it works.
 We'll use the following unsorted array:
 
 Sure! Let's sort the given unsorted array [7, 3, 2, 16, 24, 4, 11, 9]
 USING the MERGE Sort algorithm.
 
Step 1: Divide
--------------
1. Divide the array INTO two halves:
   - LEFT half: [7, 3, 2, 16]
   - RIGHT half: [24, 4, 11, 9]
 
2. Divide the LEFT half INTO two more halves:
   - LEFT half: [7, 3]
   - RIGHT half: [2, 16]
 
3. Continue dividing the sub-arrays until each one contains ONLY one element.
 
Step 2: Sort (Conquer)
-------------------------
1. Sort the leftmost sub-arrays:
   - [7, 3] (sort USING MERGE sort TO GET [3, 7])
   - [2, 16] (sort USING MERGE sort TO GET [2, 16])
 
2. Sort the rightmost sub-arrays:
   - [24, 4] (sort USING MERGE sort TO GET [4, 24])
   - [11, 9] (sort USING MERGE sort TO GET [9, 11])
 
Step 3: MERGE (Combine)
--------------------------
1. MERGE the two leftmost sub-arrays [3, 7] AND [2, 16]:
   - Compare 3 AND 2, pick 2, move TO the NEXT element IN the RIGHT array.
   - Compare 3 AND 16, pick 3, move TO the NEXT element IN the LEFT array.
   - Since the LEFT array IS exhausted, append the remaining elements FROM
   - the RIGHT array ([16]).
 
   RESULT: [2, 3, 7, 16]
 
2. MERGE the two rightmost sub-arrays [4, 24] AND [9, 11]:
   - Compare 4 AND 9, pick 4, move TO the NEXT element IN the LEFT array.
   - Compare 9 AND 24, pick 9, move TO the NEXT element IN the RIGHT array.
   - Since the RIGHT array IS exhausted, append the remaining elements FROM 
   - the LEFT array ([11]).
 
   RESULT: [4, 9, 11, 24]
 
3. Finally, MERGE the two merged sub-arrays [2, 3, 7, 16] AND [4, 9, 11, 24]:
   - Compare 2 AND 4, pick 2, move TO the NEXT element IN the LEFT array.
   - Compare 3 AND 4, pick 3, move TO the NEXT element IN the LEFT array.
   - Compare 4 AND 7, pick 4, move TO the NEXT element IN the LEFT array.
   - Compare 7 AND 9, pick 7, move TO the NEXT element IN the LEFT array.
   - Compare 9 AND 11, pick 9, move TO the NEXT element IN the LEFT array.
   - Compare 11 AND 16, pick 11, move TO the NEXT element IN the LEFT array.
   - Compare 16 AND 24, pick 16, move TO the NEXT element IN the LEFT array.
   - Since the LEFT array IS exhausted, append the remaining elements FROM 
   - the RIGHT array ([24]).
 
   RESULT: [2, 3, 4, 7, 9, 11, 16, 24]
 
 The final sorted array IS [2, 3, 4, 7, 9, 11, 16, 24], AND the MERGE Sort algorithm IS 
 complete.
 AS you can see, MERGE Sort divides the problem INTO smaller parts, sorts them individually,
 AND THEN merges them TO obtain the final sorted array.
 
 
 

Program of merge sort using python.
 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
 
    # Divide the array into two halves
    middle = len(arr) // 2
    left_half = arr[:middle]
    right_half = arr[middle:]
 
    # Recursively sort both halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
 
    # Merge the two sorted halves
    return merge(left_half, right_half)
 
def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
 
    # Compare elements from both halves and merge them in sorted order
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1
 
    # Append any remaining elements from left and right
    result.extend(left[left_idx:])
    result.extend(right[right_idx:])
 
    return result
 
# Example usage:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  

OUTPUT :
[3, 9, 10, 27, 38, 43, 82]
 

Go to Link