What is the difference between Merge Sort and Quick Sort?

Merge Sort and Quick Sort are both effective sorting algorithms with distinctive approaches, and each has its strengths and weaknesses. The main differences between Merge Sort and Quick Sort can be summarized in five points:

1. **Divide and Conquer Strategy**: Both algorithms use a divide and conquer strategy, but they apply it differently.

- Merge Sort divides the unsorted list into N sublists, each comprising one element (a list of one element is considered sorted), and then repeatedly merges the sublists to produce new sorted sublists until there is only one sublist remaining.

- Quick Sort, on the other hand, selects a ’pivot’ element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The pivot is then positioned in its proper place in the sorted array, and the process repeats for the sub-arrays on either side of the pivot.

2. **Worst-Case and Average Time Complexity**:

Merge sort performs evenly in all cases (best, average, and worst) with a time complexity of O(n log n). Quick Sort performs very well on average, with a time complexity of O(n log n), but has a worst-case scenario of O(n²), which can happen when the pivot elements are not chosen optimally, for example, in a sorted or reverse sorted array.

3. **Space Complexity**:

Merge sort requires more space, with a space complexity of O(n), as it uses auxiliary space for the temporary arrays during the merge process, while Quick Sort doesn’t require any extra space and has a space complexity of O(log n) because it sorts the elements in place.

4. **Stability**:

Merge sort is a stable sorting algorithm, meaning that equal elements maintain their relative order after sorting is performed. Conversely, Quick Sort is not inherently stable, but it can be made stable with some modifications.

5. **Usage Scenarios**:

Merge sort is often preferred for sorting linked lists because of efficient operations, high stability, and better cases when sufficient auxiliary space is present. Quick Sort is typically preferred for arrays due to in-place sorting, less space usage, and excellent average case time complexity.

Here is the pseudocode of both sorting algorithms to illustrate the approach:

1. **Merge Sort**:

MergeSort(arr[], l,  r)
If r > l
1. Find middle point to divide the array into two halves:
     middle m = l+ (r-l)/2
2. Call mergeSort for first half:
    Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
     Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
     Call merge(arr, l, m, r)

2. **Quick Sort**:

QuickSort(arr[], low, high)
If (low < high)
1. pi is partitioning index, arr[pi] is now
   at right place 
   pi = partition(arr, low, high); 

2. Separately sort elements before
   partition and after partition 
   QuickSort(arr, low, pi - 1); 
   QuickSort(arr, pi + 1, high);

6. **In-place sorting**:

Quick Sort is in-place as it does not use any extra storage while sorting. Merge Sort is out-of-place sort, it needs an extra space for temporary array.

Remember, the best choice of algorithm can vary based on specific project requirements, the characteristics of your data, and other factors.