Merge Sort Playlist - codepath/compsci_guides GitHub Wiki

Unit 7 Session 2 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Merge Sort, Recursion

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What should be returned if the playlist is empty?
    • Return an empty list.
  • How should the playlist be sorted?
    • The playlist should be sorted in alphabetical order.
  • Are all the song titles unique?
    • The problem does not specify, so assume there could be duplicates.
HAPPY CASE
Input: playlist = ["Formation", "Crazy in Love", "Halo"]
Output: ["Crazy in Love", "Formation", "Halo"]
Explanation: The playlist is sorted alphabetically.

Input: playlist = ["Single Ladies", "Love on Top", "Irreplaceable"]
Output: ["Irreplaceable", "Love on Top", "Single Ladies"]
Explanation: The playlist is sorted alphabetically.

EDGE CASE
Input: playlist = []
Output: []
Explanation: The playlist is empty, so return an empty list.

Input: playlist = ["Halo"]
Output: ["Halo"]
Explanation: The playlist contains only one song, so it is already sorted.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Merge Sort problems, we want to consider the following approaches:

  • Merge Sort: The problem can be solved by using the merge sort algorithm, which involves recursively dividing the list into smaller sublists and then merging them in sorted order.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Implement the merge sort algorithm to recursively sort the playlist.

Merge Sort Helper

Pseudocode:

1) Create an empty list `merged_playlist` to store the merged result.
2) Initialize two pointers `i` and `j` to 0 to iterate through `left_arr` and `right_arr`.
3) While both pointers are within the bounds of their respective arrays:
    a) Compare the elements at `left_arr[i]` and `right_arr[j]`.
    b) Append the smaller element to `merged_playlist` and increment the corresponding pointer.
4) If there are remaining elements in `left_arr`, append them to `merged_playlist`.
5) If there are remaining elements in `right_arr`, append them to `merged_playlist`.
6) Return the `merged_playlist`.

Merge Sort Playlist

Pseudocode:

1) Base Case: If the playlist has 1 or 0 elements, return it as it is already sorted.
2) Recursive Case:
    a) Divide the list into two halves `left_half` and `right_half`.
    b) Recursively call `merge_sort_playlist` on each half.
    c) Merge the sorted halves using `merge_sort_helper`.
    d) Return the merged list.

4: I-mplement

Implement the code to solve the algorithm.

def merge_sort_helper(left_arr, right_arr):
    # Create an empty list to store merged result list
    merged_playlist = []
    i, j = 0, 0
    
    # Use pointers to iterate through left_arr and right_arr
    while i < len(left_arr) and j < len(right_arr):
        # Compare their elements, and add the smaller element to result list
        if left_arr[i] < right_arr[j]:
            merged_playlist.append(left_arr[i])
            i += 1
        else:
            merged_playlist.append(right_arr[j])
            j += 1
    
    # Add any remaining elements from the left half
    while i < len(left_arr):
        merged_playlist.append(left_arr[i])
        i += 1
    
    # Add any remaining elements from the right half
    while j < len(right_arr):
        merged_playlist.append(right_arr[j])
        j += 1
    
    # Return the merged list
    return merged_playlist

def merge_sort_playlist(playlist):
    # Base Case: If the list has 1 or 0 elements, it's already sorted
    if len(playlist) <= 1:
        return playlist
    
    # Recursive Cases: Divide the list into two halves
    mid = len(playlist) // 2
    left_half = merge_sort_playlist(playlist[:mid])
    right_half = merge_sort_playlist(playlist[mid:])
    
    # Use the recursive helper to merge the sorted halves
    return merge_sort_helper(left_half, right_half)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through your code with the input ["Formation", "Crazy in Love", "Halo"]:
    • The merge sort should correctly sort the playlist as ["Crazy in Love", "Formation", "Halo"].

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of the playlist array.

  • Time Complexity: O(N log N) because merge sort divides the list into halves recursively (log N) and then merges them (O(N)