How to pair socks from a given pile efficiently

Key takeaways:
The problem of pairing socks from a random pile can be efficiently solved using the merge sort algorithm, which organizes the socks by their size, type, or color, making it easier to pair alike socks.
Merge sort is a divide-and-conquer algorithm that recursively divides the array (or pile of socks) into smaller subarrays, sorts them, and then merges them back into a sorted array. The process ensures all socks are placed next to their pair.
The time complexity of the merge sort algorithm is O(N*log(N)), which makes it an optimal solution for large piles of socks or arrays.
Merge sort requires O(N) auxiliary space to store the divided arrays, making it a bit costly in terms of memory usage, but still manageable for moderate-sized arrays.

Problem statement

Given a pile of socks with random distribution, we’ll find the most efficient way of pairing up the alike socks.

We model this problem by assuming an array Pile with N unique elements with exactly two instances of each element. We arrange these elements in a Pile so that each N element lies next to its partner sock. This leads to a total of 2N elements in the Pile.

Algorithm

The working of merge sort to pair socks from a given pile is as shown in the below slides:

def Merge(Pile):
  if len(Pile)<2:
    return
  else:
    m = len(Pile)//2   #array's middle element
    Right = Pile[m:]   #array's right half
    Left = Pile[:m]    #array's left half
    Merge(Right)
    Merge(Left)
    i = j = k = 0
    while i < len(Left) and j < len(Right):
      if Left[i] <= Right[j]:
        Pile[k] = Left[i]
        i += 1
      else:
        Pile[k] = Right[j]
        j += 1
      k += 1
    while i < len(Left):
      Pile[k] = Left[i]
      i += 1
      k += 1
    while j < len(Right):
      Pile[k] = Right[j]
      j += 1
      k += 1
if __name__ == '__main__':
  Pile = [4, 2, 7, 2, 4, 1, 1, 7]
  print("Unpaired socks: ", Pile)
  Merge(Pile)
  print("Paired socks: ", Pile)

Explanation:

Lines 2–3: We define the base case for recursion. The function will return if the array has just one or no elements.
Lines 5–7: Here we locate the middle element of the array and split it into left and right halves.
Lines 14–21: We a loop with two iterators that move over Left and Right subarrays, comparing their elements and merging the smaller ones into Arr.
Lines 23–31: We check if there is still any element left in the Left or Right subarrays to merge into Arr.

Time and space complexities

The time complexity of this recursive algorithm is O(N*log(N)). It uses auxiliary space for storing the array elements then its space complexity is O(N).

Frequently asked questions

Haven’t found what you were looking for? Contact Us

How can I pair socks from a pile efficiently?

You can pair socks efficiently using the Merge Sort algorithm, which sorts the socks by size, type, or color. This ensures that similar socks are placed next to each other, allowing for quick pairing.

How do you pair socks quickly?

To pair socks quickly, sort them first by characteristics like color or size. Once sorted, socks that are alike will be adjacent, making the pairing process faster.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments