Merge Sort

 

Our Objective

To implement a program that sort an array of elements using Merge Sort. 

 

The Theory

Merge Sort is a popular sorting algorithm that uses the divide and conquer approach to sort an array. The Merge Sort algorithm works by dividing the array into two halves repeatedly until each sub-array contains only one element. Then it merges the sub-arrays in a sorted manner until the original array is sorted.

The program starts with the "mergeSort" function, which takes three arguments - the array to be sorted (arr), the starting index of the array (l), and the ending index of the array (r). If the starting index is less than the ending index, it calculates the middle index m of the array and recursively calls "mergeSort" on the left half of the array and the right half of the array. This recursive call continues until each sub-array contains only one element.

Once the sub-arrays are sorted, the "merge" function is called to merge them. The "merge" function takes four arguments - the array to be sorted (arr), the starting index of the left sub-array (l), the ending index of the left sub-array and the starting index of the right sub-array (m), and the ending index of the right sub-array (r).

The "merge" function creates two sub-arrays - "L" and "R" - to store the left and right halves of the original array. It then iterates over these sub-arrays, comparing the elements and merging them into a new sorted array. Once one of the sub-arrays has been completely merged, the function appends the remaining elements of the other sub-array to the end of the sorted array.

 

Learning Outcomes 

  • Understand the Merge Sort algorithm and its implementation in Python.
  • Explain the divide and conquer approach used in the Merge Sort algorithm to sort an array.
  • Describe the purpose and functionality of the merge and mergeSort functions.
  • Understand the parameters passed to each function and their roles in the sorting process.
  • Identify the use of loops and conditional statements in the program to sort the array.
  • Understand the importance of sorting algorithms in computer science and their applications in real-world scenarios.
  • Implement the Merge Sort algorithm to sort an array of integers or other data types in Python.