Tag: merge-sort

Merge Sort

Imagine chopping a messy pile of vegetables into smaller pieces, sorting each pile individually, and then merging them back into a perfectly organized whole. That’s the essence of Merge Sort, dividing, sorting, and conquering data to achieve order.

Process

Merge Sort, unlike its comparison-based counterparts, takes a divide-and-conquer approach, resembling how a ruler conquers territories! Let’s dive into the steps:

1. Divide: Imagine the data as a kingdom waiting to be organized. The king (Merge Sort) divides the kingdom (data) into smaller provinces (sub-lists) of roughly equal size.

2. Conquer: Each province undergoes its own mini-conquest. If a province has only one element (citizen), it’s already sorted! Otherwise, the algorithm recursively divides and conquers each province further, breaking them down into even smaller units until each has only one element.

3. Merge and Rule: Once all provinces are single-element kingdoms, the real merging magic begins. The algorithm starts from the smallest conquered provinces and strategically combines them. Imagine two conquered provinces (sorted sub-lists) merging like neighboring kingdoms, carefully comparing and placing citizens (elements) in their rightful order to form a larger, sorted province.

4. Repeat and Expand: This merging continues, combining two sorted provinces at a time, creating larger and larger sorted territories. It’s like the conquered provinces forming alliances, growing in size and order until the entire kingdom (data) is united under the banner of a single, perfectly sorted list.

Pseudo Code

Code
function mergeSort(array):
  if length(array) <= 1:
    return array

  mid = floor(length(array) / 2)
  left = mergeSort(subarray(array, 0, mid))
  right = mergeSort(subarray(array, mid + 1, length(array)))

  return merge(left, right)

function merge(left, right):
  merged = []
  while length(left) > 0 and length(right) > 0:
    if first element of left <= first element of right:
      append first element of left to merged
      remove first element from left
    else:
      append first element of right to merged
      remove first element from right
  append remaining elements of left to merged
  append remaining elements of right to merged
  return merged

function subarray(array, start, end):
  # Creates a new subarray from the original array with specified start and end indices
  new_array = []
  for i in range(start, end):
    append element at index i of array to new_array
  return new_array
Explanation

mergeSort(array):

  • if length(array) <= 1: If the array has only one element or less, it’s already considered sorted and returned as-is.
  • mid = floor(length(array) / 2): Calculates the middle index of the array for dividing it into approximately equal halves.
  • left = mergeSort(subarray(array, 0, mid)): Recursively calls mergeSort on the left half of the array (from index 0 to mid-1).
  • right = mergeSort(subarray(array, mid + 1, length(array))): Recursively calls mergeSort on the right half of the array (from index mid+1 to the end).
  • return merge(left, right): Calls the merge function to combine the two sorted halves (left and right) into a single sorted array and returns it.

merge(left, right):

  • merged = []: Creates an empty array to store the merged result.
  • while length(left) > 0 and length(right) > 0: Continues the loop as long as both halves have elements left.
    • if first element of left <= first element of right:
      • append first element of left to merged: Adds the smaller element from the left half to the merged array.
      • remove first element from left: Removes the added element from the left half.
    • else:
      • append first element of right to merged: Adds the smaller element from the right half to the merged array.
      • remove first element from right: Removes the added element from the right half.
  • append remaining elements of left to merged: Appends any remaining elements in the left half to the merged array.
  • append remaining elements of right to merged: Appends any remaining elements in the right half to the merged array.
  • return merged: Returns the final sorted array after merging both halves.

subarray(array, start, end):

  • new_array = []: Creates a new empty array.
  • for i in range(start, end): Iterates through the elements from the specified start index to (but not including) the end index.
    • append element at index i of array to new_array: Adds the element at the current index (i) from the original array to the new_array.
  • return new_array: Returns the newly created subarray containing the specified elements.

Implementations

Kotlin

Golang