Multithreaded Quick Sort

Quick sort is a classic example where we can use multiple threads, since execution proceeds on separate paths on separate segments. You can read about classic Quick Sort here.

Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately

Now check the last step, The two segments can be sorted and processes by 2 separate Threads easily as they don't depend on each other. In turn they can spawn more segments and more threads. For this we can use ThreadPool.

Multi-threaded Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately via Two Threads

INPUT

2

6

7

5

3

1

8

4

PROCESSING

2

6

7

5

3

1

8

4

2

8

7

5

3

1

4

6

2

1

7

5

3

4

8

6

2

1

3

5

4

7

8

6

2

1

3

4

5

7

8

6

THREAD 1 2 1 3	THREAD 2 5 7 8 6
1 2 3	5 7 6 8 5 6 7 8

FINAL RESULT

1

2

3

4

5

6

7

8

Quick Sort

QuickSort works on the concept of dividing and proceeding.

An array is divided into two segments, One containing all small elements, other containing all higher elements (from a pivot element). The two segments are in-turn QuickSorted to get the sorted output.

Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately.

INPUT

2

6

7

5

3

1

8

4

PROCESSING (4 is the pivot)

2

6

7

5

3

1

8

4

2

8

7

5

3

1

4

6

2

1

7

5

3

4

8

6

2

1

3

5

4

7

8

6

2

1

3

4

5

7

8

6

Pivot (4) is in place now. Time to QuickSort separate segments

2 1 3	5 7 8 6
1 2 3	5 7 6 8 5 6 7 8

FINAL RESULT

1

2

3

4

5

6

7

8

Coming Soon: Quick Sort Java Code