Merge Sort for Linked Lists Hard 0 attempts
GeeksforGeeks ↗

Merge Sort for Linked Lists

Hard Linked List GeeksforGeeks

Sort a linked list by applying the merge sort algorithm. The list is given here as an array; return it in sorted order. Merge sort works by repeatedly splitting the list in half, sorting each half recursively, and then merging the two sorted halves back into one.

Input Format
Implement mergeSortForLinkedLists(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
arr = [4,2,1,3]
Output
[1,2,3,4]

Example 2

Input
arr = [-1,5,3,4,0]
Output
[-1,0,3,4,5]
Constraints
  • 0 <= number of nodes <= 5 * 10^4
  • -10^5 <= Node.val <= 10^5
Test Cases (2)
Case 1
Args: [[4,2,1,3]] Expected: [1,2,3,4]
Case 2
Args: [[-1,5,3,4,0]] Expected: [-1,0,3,4,5]
Topics
Linked List

Approach: Recursive Merge Sort

Split the array in half, recursively sort both halves, then merge them using two pointers. This mirrors the linked list approach where you split with slow/fast pointers and merge sorted sublists.

javascript
function mergeSortForLinkedLists(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSortForLinkedLists(arr.slice(0, mid));
  const right = mergeSortForLinkedLists(arr.slice(mid));
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length)
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  return result.concat(left.slice(i), right.slice(j));
}

Time Complexity: O(n log n)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript