Kunal Saxena
BAN USER@steephen 's answer explains about game implementation.
There are other things to consider in this problem (Related to Design and Scalability)
Read -- github.com/tim-hr/stuff/wiki/System-design:-How-would-you-design-a-two-player-online-chess-game%3F
It is better to use Redis for auth tokens and sessions. Gameplay data can be stored in RDBMS or NoSQL if you want resume feature.
Coming to notification point, Let's have a scenario where you are waiting for an opponent. Cases will be
-> apps can easily have push notification.
-> for web-based games there are web-notifications
-> if any of above doesn't fit then we can create a game and same time create 1 topic ("nextGamePair") using JMS or RabbitMQ.
Every user waiting for the opponent will subscribe to this topic. When there are 2 players subscribe, we will start a game with those 2 players and unsubscribe them from the topic.
With 1 Topic we will handle this for all users.
All these things will cover aspects of this problem.
But that will be the best case of insertion sort. It will take O(n^2) in average and worst case.
- Kunal Saxena December 03, 2017
This is insertion sort.
> if elements are already sorted, it won't make any swap
start of the unsorted array -> element for which line arr[j+1] = arr[j]; will start executing.
- Kunal Saxena January 25, 2018end of unsorted array -> element for which line arr[j+1] = arr[j]; will stop executing.
{start,....., end} will be min unsorted array.
There could be multiple such unsorted arrays. To find that, store all (start, end) and finally calculate one subarray with min length.
Time Complexity:- Since most of the elements are sorted, this will take between O(n) and O(n^2).