Merge Sort Implementation Using Linked Lists #357

[amanvatss]

Description:

1. Summary of Changes:

   • Implemented Merge Sort algorithm for Linked List in the project.
   • The function sorts a linked list by dividing it into two halves, recursively sorting each half, and merging the sorted halves together.

2. Fixes:

   • This change addresses the issue of inefficient sorting algorithms previously used for linked lists, which may not perform well on large data sets.

4.Motivation and Context:

• The motivation behind this change was to improve sorting performance for linked lists in the project.
• Merge sort is chosen because it has a time complexity of O(n log n), which is optimal for sorting linked lists. Unlike quicksort, merge sort is stable and does not require extra space, making it ideal for linked list sorting.

5. Dependencies:

   • No additional dependencies are required for this change. The existing linked list data structure is sufficient to implement the merge sort.

Fixes #357

Type of change:

• [x] New feature (non-breaking change which adds functionality)

Checklist:

• [x] My code follows the style guidelines of this project.
• [x] I have performed a self-review of my own code.
• [x] I have commented my code, particularly in hard-to-understand areas.
• [x] My changes generate no new warnings.
• [x] I have added tests that prove my fix is effective or that my feature works.
• [x] I have added the file in the correct directory

Screenshots / Video:

[Kavya-24]

Marking this as hacktoberfest-