Our Objective

To implement a program to sort a list / array using merge sort algorithm.

The Theory

The program takes an input list of integers 'arr', and first prints the original list using the 'printList()' function. Then, the program calls the 'mergeSort()' function to sort the input list. After the sorting is completed, the program prints the sorted list again using the 'printList()' function.

The 'mergeSort()' function first checks if the length of the input list is greater than 1. If the length is greater than 1, it calculates the middle index of the list and splits the input list into two sub-lists: 'L' and 'R', where 'L' contains the left half of the list and 'R' contains the right half. The function then recursively calls itself with 'L' and 'R' as input, until the length of both 'L' and 'R' becomes 1.

After the recursive calls return, the function merges the two sub-lists by comparing the elements of 'L' and 'R', and adding the smaller element to the final sorted list 'arr'. This process continues until all elements of 'L' and 'R' have been added to 'arr'.

Finally, the 'printList()' function takes a list as input and prints each element of the list, separated by a space.

Divide and Conquer strategy

The divide and conquer strategy is a problem-solving approach in computer science and mathematics that involves breaking down a complex problem into smaller subproblems, solving them independently, and then combining the solutions to solve the original problem. The name comes from the three main steps involved:

1. Divide: Break the original problem down into smaller, more manageable subproblems.
2. Conquer: Solve the subproblems independently.
3. Combine: Combine the solutions to the subproblems to solve the original problem.

The divide and conquer strategy is often used to solve problems that are difficult to solve directly, such as sorting algorithms, matrix multiplication, and finding the closest pair of points in a set.

The main advantage of the divide and conquer strategy is that it allows for parallel processing of the subproblems, which can result in faster processing times. Additionally, it can be easier to reason about and debug smaller subproblems rather than the original, larger problem.

Some common algorithms that use the Divide and Conquer strategy include:

• Merge Sort: A sorting algorithm that divides the input array into two halves, sorts each half independently, and then merges the sorted halves back together.
• Quick Sort: A sorting algorithm that partitions the input array into two subarrays around a pivot value, recursively sorts the subarrays, and then combines the sorted subarrays.
• Binary Search: A search algorithm that divides the input array in half at each step, reducing the search space until the desired value is found.

Learning Outcomes 

By learning the Divide and Conquer algorithm to find the maximum value of an array, you can achieve several learning outcomes, including:

• Understanding of Divide and Conquer algorithm: You will gain an understanding of the Divide and Conquer algorithm, which involves breaking down a problem into smaller sub-problems, solving each sub-problem independently, and then combining the solutions to solve the original problem.
• Problem-solving skills: You will develop problem-solving skills by identifying and solving the problem of finding the maximum value in an array using the Divide and Conquer algorithm.
• Analytical skills: You will improve your analytical skills by analyzing the time complexity of the Divide and Conquer algorithm and comparing it with other algorithms for finding the maximum value in an array.
• Debugging skills: You will learn to debug your code by identifying and resolving errors that occur during the implementation of the algorithm.
• Optimization skills: You will learn to optimize the algorithm by identifying and removing any redundancies in the code and improving the time complexity of the algorithm.